Кратчайшие пути в графах: Дейкстра, Беллман-Форд и поиск в DAG

Процедура релаксации (Relaxation)

cpp

void relax(int u, int v, int w, vector<int>& d, vector<int>& p) {
    if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        p[v] = u;
    }
}

6 фундаментальных свойств кратчайших путей:

Неравенство треугольника:

\delta(s, v) \le \delta(s, u) + w(u, v)

;

Свойство верхней границы:

d[v] \ge \delta(s, v)

всегда;

Свойство сходимости: если

u \to v

на кратчайшем пути и

d[u] = \delta(s, u)

, то после релаксации

(u, v)

получаем

d[v] = \delta(s, v)

;

Свойство отсутствия пути: если пути нет,

d[v] = \infty

;

Свойство ослабления пути;

Свойство подграфа предшествования.

1. Алгоритм Дейкстры: $O((V + E) \log V)$ (для $w \ge 0$ )

cpp

vector<int> dijkstra(int s, int n, const vector<vector<pair<int, int>>>& adj) {
    vector<int> dist(n, 1e9);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

2. Алгоритм Беллмана-Форда: $O(V \cdot E)$

Выполняет $V-1$ итерацию релаксации всех ребер. Если на $V$ -м проходе какое-то расстояние уменьшается — в графе есть цикл отрицательного веса!

Кратчайшие пути в графах: Дейкстра, Беллман-Форд и поиск в DAG

Процедура релаксации (Relaxation)

6 фундаментальных свойств кратчайших путей:

1. Алгоритм Дейкстры: O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV) (для w≥0w \ge 0w≥0)

2. Алгоритм Беллмана-Форда: O(V⋅E)O(V \cdot E)O(V⋅E)

Что дальше?

1. Алгоритм Дейкстры: $O((V + E) \log V)$ (для $w \ge 0$ )

2. Алгоритм Беллмана-Форда: $O(V \cdot E)$