Коротко — ограничение, почему Dijkstra не годится, как его обойти, и сравнение с Беллман–Форд.
1) Ограничение Dijkstra
- Алгоритм корректен только при неотрицательных весах рёбер. Гарантия основана на жадности: когда вершина извлечена из очереди (минимальное расстояние "зафиксировано"), это расстояние действительно минимально только если все оставшиеся рёбра имеют неотрицательный вклад.
- При наличии отрицательных рёбер жадный выбор может «зафиксировать» неминимальное расстояние и дальнейшие релаксации не исправят его.
2) Контрпример (простой)
- Вершины: $A,B,C$.
- Рёбра: $A\to B$ вес $2$, $A\to C$ вес $1$, $C\to B$ вес $-2$.
- Источник $A$.
Шаги Dijkstra:
- Инициализация: $d(A)=0,d(B)=2,d(C)=1$.
- Извлекается $C$ ($d(C)=1$), релакс $C\to B$: даёт $d(B)=1+(-2)=-1$, обновление возможно.
- Но если вместо этого (в другом порядке) извлечён был бы $B$ раньше (например, при реализации, где $B$ попал с приоритетом 2 и застолблен), Dijkstra может "зафиксировать" $d(B)=2$ и дальше не пересчитать в $-1$. Это показывает, что поведение зависит от порядка и жадная фиксация неверна при отрицательных рёбах.
(Примечание: в реальной корректной реализации Dijkstra на приоритетной очереди такой порядок извлечения по текущим ключам обычно вынесет $C$ раньше $B$ в этом примере; идея в том, что наличие отрицательного ребра разрушает гарантии: в более сложных примерах фиксация может произойти неверно.)
3) Как обойти проблему
- Если нужны SSSP (single-source) и есть отрицательные рёбра (но нет отрицательных циклов reachable), используйте Беллман–Форд: он корректен и обнаруживает отрицательные циклы.
- Если нужны APSP (all-pairs) и граф может содержать отрицательные рёбра (без отрицательных циклов) — используйте алгоритм Джонсона:
- Запустите Bellman–Ford от добавленной вершины $s$ к каждой вершине, получите потенциалы $h(v)$.
- Перевзвесьте рёбра: $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)$. Тогда все $w^{\prime }(u,v)\ge 0$.
- Запустите Dijkstra из каждой вершины по неположительным весам $w^{\prime }$ и восстановите оригинальные расстояния: $d(u,v)=d^{\prime }(u,v)-h(u)+h(v)$.
- Если граф ацикличен (DAG), можно найти кратчайшие пути в топологическом порядке за $O(V+E)$ даже с отрицательными рёбрами.
- Простая идея «прибавить константу ко всем рёбам» не работает для сохранения порядка кратчайших путей, поэтому корректное решение — либо Bellman–Ford, либо пере-взвешивание (Johnson).
4) Сравнение по сложности и применимости
- Dijkstra (один источник):
- с бинарной кучей: $O((V+E)\log V)$ (часто пишут $O(E\log V)$ для связных графов),
- с Fibonacci-кучей: $O(E+V\log V)$.
- Требование: все веса $\ge 0$.
- Bellman–Ford (один источник):
- $O(VE)$.
- Плюсы: корректен при отрицательных весах, обнаруживает отрицательные циклы.
- Минусы: значительно медленнее на разреженных графах.
- Johnson (для всех пар):
- Стоимость: один запуск Bellman–Ford $O(VE)$ + $V$ запусков Dijkstra. С Fibonacci-кучей итог: $O(VE+V^2\log V)$.
- Применимость: подходит для APSP в графах с отрицательными рёбрами, но без отрицательных циклов; часто выгоднее, чем классический Floyd–Warshall ($O(V^3)$) для разреженных графов.
- Floyd–Warshall (APSP, простой вариант): $O(V^3)$, работает с отрицательными рёбрами, но требует отсутствия отрицательных циклов для корректных конечных расстояний.
5) Выводы кратко
- Dijkstra — быстрый для неотрицательных весов, но некорректен при отрицательных рёбах.
- Bellman–Ford — корректен при отрицательных рёбах и обнаруживает отрицательные циклы, но медленнее ($O(VE)$).
- Johnson — комбинирует Bellman–Ford и Dijkstra для APSP при наличии отрицательных рёбер (без отрицательных циклов), часто наиболее эффективен для разреженных графов.
Если нужно, могу привести полный пошаговый разбор конкретного примера работы Dijkstra и Bellman–Ford на одном и том же графе.