Коротко и формально.
1) Утверждение корректности (для неотрицательных весов)
- Обозначения: граф с вершинами $V$, рёбра $(u,v)$ с весами $w(u,v)\ge 0$. Исток $s$. Пусть $\delta (s,v)$ — длина кратчайшего пути $s\to v$. Алгоритм хранит оценки $d[v]$, и множество уже «закреплённых» вершин $S$. Инициализация: $d[s]=0$, остальные $d=\infty$. На каждом шаге выбирается $u\notin S$ с минимальным $d[u]$, добавляется в $S$ и выполняется релаксация всех исходящих рёбер.
- Инвариант (для доказательства по индукции): при любом моменте для всех $x\in S$ выполнено $d[x]=\delta (s,x)$. Кроме того, для всех $v$ всегда $d[v]\ge \delta (s,v)$ (оценка не меньше истинной длины, т.к. $d[v]$ — длина некоторого обнаруженного пути).
- Базовый шаг: $S=\{s\}$, $d[s]=0=\delta (s,s)$.
- Индукционный переход: пусть инвариант верен для множества $S$. Пусть $u$ — вершина вне $S$ с минимальным $d[u]$. Рассмотрим некоторый кратчайший путь $P$ от $s$ до $u$. Пусть $y$ — первая на $P$ вершина, не лежащая в $S$, а $x$ — её предшественник на $P$ (тогда $x\in S$). По индукции $d[x]=\delta (s,x)$. Когда $x$ был добавлен в $S$, ребро $(x,y)$ было релаксировано, значит после обработки $x$ выполнено
$$d[y]\le d[x]+w(x,y)=\delta (s,x)+w(x,y)=\delta (s,y).$$ Так как $u$ выбран с минимальным $d$ среди вершин вне $S$, имеем $d[u]\le d[y]$. Отсюда
$$d[u]\le d[y]\le \delta (s,y)\le \delta (s,u),$$ причём всегда $d[u]\ge \delta (s,u)$. Следует $d[u]=\delta (s,u)$. То есть инвариант сохраняется при добавлении $u$.
- Заключение: после завершения все $d[v]=\delta (s,v)$. Ключевой момент — неотрицательность весов $w(u,v)\ge 0$, которая обеспечивает монотонность оценок и справедливость выбора вершины с минимальным $d$.
2) Ограничения при наличии отрицательных весов
- Если существуют ребра с отрицательным весом, жадный выбор вершины с наименьшим $d$ может дать неверный окончательный результат: может существовать путь к уже «закреплённой» вершине через ещё не обработанные вершины с суммарным отрицательным вкладом, делающим этот путь короче. Пример:
вершины $s,a,b,c$, рёбра: $s\to a$ вес $0$, $s\to b$ вес $2$, $b\to c$ вес $-5$, $c\to a$ вес $2$. Кратчайший путь $s\to b\to c\to a$ имеет длину $-1$, но Dijkstra сначала закрепит $a$ с $d[a]=0$ и не учтёт более короткий маршрут.
- Следствие: для гарантированной корректности алгоритма Dijkstra требуется неотрицательность всех весов на всех рёбрах, доступных из достижимых вершин. При отрицательных рёбрах никаких простых «локальных» исправлений не дают гарантию корректности во всех случаях.
- Дополнительно: если присутствуют отрицательные циклы, задача о кратчайшем пути в классическом смысле не определена (короче пути можно сделать сколь угодно).
3) Альтернативы для графов с отрицательными весами
- Bellman–Ford (одиночный источник):
- Работает при произвольных весах (позволяет отрицательные), обнаруживает отрицательные циклы (если после $V-1$ итераций можно ещё релаксировать — есть отрицательный цикл).
- Сложность: $O(VE)$.
- Подход: релаксировать все рёбра последовательно $V-1$ раз; если после этого возможно улучшение — негативный цикл.
- Johnson (все-пары кратчайших путей, для разреженных графов):
- Сначала запускает Bellman–Ford от дополнительной вершины, чтобы получить потенциалы $h(v)$. Затем переопределяет веса:
$$w^{\prime }(u,v)=w(u,v)+h(u)-h(v),$$ что гарантирует $w^{\prime }(u,v)\ge 0$ и сохраняет относительные расстояния между парами вершин.
- После этого запускает Dijkstra от каждой вершины на графе с весами $w^{\prime }$ и восстанавливает оригинальные расстояния:
$$\delta (u,v)={\delta }^{\prime }(u,v)-h(u)+h(v).$$ - Сложность: одна итерация Bellman–Ford $O(VE)$ + $V$ запусков Dijkstra. Итог:
- с бинарной кучей для Dijkstra: $O(VE+V(E+V)\log V)$,
- с фибоначчиевой кучей: $O(VE+V^2\log V)$ (т.к. один запуск Dijkstra — $O(E+V\log V)$).
- Johnson эффективен на разреженных графах ($E\ll V^2$). Требует отсутствия отрицательных циклов.
- Floyd–Warshall (все-пары, простой матричный метод):
- Работает для произвольных весов (может обнаружить негативные циклы по отрицательным диагоналям).
- Сложность: $O(V^3)$. Удобен для плотных графов или когда $V$ невелик.
- Выбор алгоритма:
- Если все веса неотрицательны и нужен single-source — Dijkstra (структура куч решает константы).
- Если возможны отрицательные веса и нужен single-source — Bellman–Ford.
- Если нужны все-пары и граф разрежен — Johnson.
- Если все-пары и граф плотный или $V$ невелик — Floyd–Warshall.
Краткие сложности (итог):
- Dijkstra: массив — $O(V^2)$, бинарная куча — $O((E+V)\log V)$, фибоначчиева куча — $O(E+V\log V)$.
- Bellman–Ford: $O(VE)$.
- Johnson: $O(VE+V\cdot T_{Dijkstra})$ → с фиб. кучей $O(VE+V^2\log V)$.
- Floyd–Warshall: $O(V^3)$.
Если нужно, могу привести формализованное доказательство с шагами релаксации и полным псевдокодом и/или примеры сравнения на конкретных графах.