Алгоритм Дейкстры
Содержание
Задача
Дан граф $G=(V, E)$ (возможно, ориентированный), все рёбра которого имеют неотрицательный вес. В $G$ выделена вершина $s$ и нужно найти кратчайшие расстояния от $s$ до всех вершин в графе.
Лемма
Разобьём $|V|$ на $2$ множества: $visited$ $~-$ содержащее $start$ $~-$ и $V \setminus visited$. Пусть для всех вершин в $visited$ мы уже посчитали кратчайшие расстояния. Рассмотрим среди вершин из $V \setminus visited$ только те, которые соединены ребром хотя бы с одной из вершин $visited$. Теперь выберем из оставшихся вершин в $V \setminus visited$ такую $u$, для которой величина, равная $\min_{v, v \in In(u)} \rho (s, v) + w(v, u)$ минимальна. Тогда для $u$ верно, что $\rho(s, u) = \min_{v, v \in In(u)} \rho (s, v) + w(v, u)$.
Доказательство
Пусть не так. Тогда существует путь из $s$ в $u$, длина которого меньше описанной выше величины. Рассмотрим первое ребро на этом пути, начало которого ($v'$) лежит в $visited$, а конец ($u'$) $~-$ нет. Заметим тогда, что путь от $s$ до $u'$ заведомо не длиннее пути $s ~- v' - u' ~- u$, который, в свою очередь, по предположению от противного, короче пути, который рассматривается в лемме (берём для $u$ вершину $v$ и $visited$, для которой $\rho (s, v) + w(v, u)$ минимально). Но тогда вершина $u$ не минимальна в том смысле, в которой заявляется в лемме $~-$ мы нашли вершину $u'$ не из $visited$ и смежную с ней $v'$ из $visited$, для которых расстояние $s ~- v' - u'$ меньше, чем такое же для $u$. Противоречие.
Описание алгоритма
- В начале $dist[s] = 0$, $dist[ V \setminus \{s\}] = INF$
- На каждом шаге алгоритма мы выбираем из ещё не рассмотренных вершин минимальную в смысле леммы выше. Для этого мы, добавляя в $visited$ очередную вершину, просматриваем всех её соседей и улучшаем для каждого из них оценку сверху на длину кратчайшего пути
- Заканчиваем алгоритм мы через |V| итераций.
Как брать минимальную вершину?
Это можно делать двумя способами:
- Каждый раз заново перебирать все вершины и брать минимальную. В таком случае сложность алгоритма становится $O(\underbrace{V^2}_\text{на каждой из V итераций рассматриваем все вершины} + \underbrace{E}_\text{суммарно на всех шагах мы рассмотрим каждое ребро по 2 раза})$.
- Поддерживать отсортированный список пар (например, с помощью std::set) вида (dist[v], v), где в dist[v] хранится текущая оценка сверху на минимальное расстояние. В этом случае сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$
Реализация
За $V^2 + E$
typedef int Vertex;
typedef long long dist_t;
vector<dist_t>
ShortestDistancesDijkstra(vector<vector<int> >& adjacent, /* граф, хранимый списками смежности */
Vertex start) {
int n = adjacent.size();
vector<dist_t> dist(n, INF);
dist[start] = 0LL;
vector<bool> is_visited(n, false);
for (int iter_n = 0; iter_n < n; ++iter_n) {
// ============== Выбираем ближайшую непосещённую ==============
Vertex closest_not_visited = -1;
dist_t closest_dist = INF;
for (Vertex v = 0; v < n; ++v) {
if (!is_visited[v] && dist[v] < closest_dist) {
closest_dist = dist[v];
closest_not_visited = v;
}
}
is_visited[closest_not_visited] = true;
// ============== Релаксируем рёбра, идущие из неё ==============
for (auto&& [to, w] : adjacent[closest_not_visited]) {
dist[to] = min(dist[to], dist[closest_not_visited] + w;
}
}
return dist;
}
За $(E+V)logV$
typedef int Vertex;
typedef long long dist_t;
vector<dist_t>
ShortestDistancesDijkstra(vector<vector<int> >& adjacent, /* граф, хранимый списками смежности */
Vertex start) {
int n = adjacent.size();
vector<dist_t> dist(n, INF);
dist[start] = 0LL;
set<pair<dist_t /* dist[v] */,
Vertex /* v */ >
> not_visited_dist;
for (Vertex v = 0; v < n; ++v) {
not_visited.insert({dist[v], v});
}
while (!not_visited_dist.empty()) {
// ============== Выбираем ближайшую непосещённую ==============
auto&& [closest_d, closest_not_visited] = *not_visited_dist.begin();
not_visited_dist.erase(begin);
// ============== Релаксация рёбер из неё ==============
for (auto&& [to, w] : adjacent[closest_not_visited]) {
if (dist[to] > dist[closest_not_visited] + w) {
not_visited_dist.erase({dist[to], to});
dist[to] = dist[closest_v] + w;
not_visited_dist.insert({dist[to], to});
}
}
}
return dist;
}
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex