Кратко и по сути — набор подходов и условия применения.
1) Алгоритмы для задачи кратчайшего пути (ориентированный взвешенный граф)
- Дейкстра (один источник, неотрицательные веса): наивная реализация $O(V^2)$, с кучей (binary heap) $O((V+E)\log V)$ (обычно пишут $O(E\log V)$ для связных графов). Гарантирует корректность при всех весах ребер $\ge 0$.
- Беллман–Форд (один источник, допускаются отрицательные веса): корректен при наличии отрицательных ребер и умеет обнаруживать отрицательные циклы, сложность $O(VE)$.
- SPFA (вариант Беллман–Форда на очереди): часто быстрее на практических данных, но в худшем случае сложность $O(VE)$; возможны зацикливания при отрицательных циклах, поэтому нужен контроль итераций/детекция.
- Для DAG (ацикличный ориентированный граф): релаксация вершин в топологическом порядке за $O(V+E)$ и работает при отрицательных весах.
- Для задачи «все пары кратчайших путей»: Флойд–Уоршелл $O(V^3)$ (поддерживает отрицательные веса и детектирует отрицательные циклы), или Джонсон — пере-взвешивание с помощью Беллман–Форда + многократный запуск Дейкстры: сложность примерно $O(VE+V^2\log V)$ (в зависимости от реализации кучи).
2) Когда Дейкстра неприменим и почему
- Дейкстра требует неотрицательных весов всех ребер. При наличии хотя бы одного отрицательного ребра алгоритм может дать неверный результат.
- Причина: Дейкстра опирается на жадное утверждение «когда вершина извлечена из очереди (минимальное текущее расстояние), её расстояние окончательно». С отрицательными рёбрами позже может появиться путь, который уменьшит уже «зафиксированное» расстояние.
Пример неработающего случая (малый граф):
- Вершины $S,A,B,C$. Рёбра: $S\to A:2$, $S\to B:3$, $B\to A:-4$, $A\to C:2$.
- Истинный кратчайший путь $S\to B\to A\to C$ имеет длину $3-4+2=1$. Дейкстра зафиксирует $A$ как $2$ (через $S\to A$) и уже не учтёт более короткий путь через $B$, поэтому найдёт для $C$ длину $4$ вместо $1$.
3) Альтернативные решения
- Если есть отрицательные веса, но нет отрицательных циклов, используйте Беллман–Форд (один источник) — $O(VE)$, или для всех пар — Джонсон (Беллман–Форд для пере-взвешивания + Дейкстра из каждой вершины).
- Если присутствуют отрицательные циклы, до вопроса «кратчайший путь» для достижимых из источника вершин нет корректного конечного ответа (расстояние стремится в $-\infty$); Беллман–Форд способен обнаружить такие циклы.
- Для DAG используйте топологическую сортировку и релаксацию за $O(V+E)$.
- SPFA может быть практичным ускорением Беллман–Форда, но осторожно — в худшем случае медленнее и нестабилен при специальных графах.
Краткая рекомендация выбора:
- Все веса $\ge 0$, один источник: Дейкстра.
- Есть отрицательные веса, нужно один источник: Беллман–Форд (или SPFA с оговорками).
- Есть отрицательные веса, нужно все-пары: Джонсон (если нет отрицательных циклов) или Флойд–Уоршелл.
- Граф ацикличен: алгоритм по топологическому порядку.