Алгоритм Дейкстры

Задача

Дан граф $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| итераций.

Как брать минимальную вершину?

Это можно делать двумя способами:

1. Каждый раз заново перебирать все вершины и брать минимальную. В таком случае сложность алгоритма становится $O(\underbrace{V^2}_\text{на каждой из V итераций рассматриваем все вершины} + \underbrace{E}_\text{суммарно на всех шагах мы рассмотрим каждое ребро по 2 раза})$.
2. Поддерживать отсортированный список пар (например, с помощью std::set) вида (dist[v], v), где в dist[v] хранится текущая оценка сверху на минимальное расстояние. В этом случае сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex