Коротко: Дейкстра некорректен на графах с отрицательными рёбрами, потому что его инвариант «как только вершина извлечена — расстояние до неё окончательное» нарушается: более короткий путь с отрицательным ребром может появиться позже и снизить расстояние до уже «зафиксированной» вершины.
Пример (минимальный). Вершины $s,u,v$ и рёбра:
$s\to u$ вес $2$, $s\to v$ вес $1$, $u\to v$ вес $-2$.
Изначально $d(s)=0,d(u)=2,d(v)=1$. Дейкстра извлекает $v$ (так как $1<2$) и помечает его окончательным. Но путь $s\to u\to v$ даёт расстояние $2+(-2)=0$, что меньше $1$. Поскольку $v$ уже зафиксирован, алгоритм не учтёт это улучшение — результат неверен.
Ключевая причина формально: Дейкстра опирается на то, что для любого извлечённого вершина $x$ и любого пути через ещё не обработанные вершины расстояние через них не может быть меньше $d(x)$. Это верно только если все веса неотрицательны.
Что делать с негативными весами — альтернативы:
- Bellman–Ford:
- Работает при отрицательных весах и обнаруживает отрицательные циклы, достижимые из источника.
- Сложность $O(VE)$.
- Используйте, если нужен один источник и есть отрицательные веса.
- SPFA (очередной вариант Bellman–Ford с улучшениями):
- Часто быстрее на практике, но в худшем случае может быть экспоненциальным или $O(VE)$.
- Ненадёжен в злонамеренных случаях; полезен для практических задач, но с осторожностью.
- Johnson для всех-пар кратчайших путей:
- Сначала запускает Bellman–Ford от фиктивной вершины, чтобы получить потенциалы $h(v)$ (проверяет отрицательные циклы). Затем перевзвешивает рёбра $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)$ — все $w^{\prime }$ неотрицательны — и запускает Dijkstra из каждой вершины.
- Сложность примерно $O(VE+V\cdot (\text{Dijkstra}))$ (для разреженных графов выгодно).
- Floyd–Warshall:
- Для всех пар, проста в реализации, поддерживает отрицательные веса и обнаруживает отрицательные циклы.
- Сложность $O(V^3)$ — подходит для небольших $V$.
Дополнительно:
- Если в графе есть отрицательные циклы, достижимые из источника, то кратчайшие пути не определены (стягиваются в $-\infty$). Любой алгоритм должен либо обнаружить такие циклы (Bellman–Ford, Floyd–Warshall), либо сообщить об их существовании.
- Если все веса неотрицательны, Дейкстра остаётся оптимальным выбором по эффективности.
Резюме: для графов с отрицательными весами используйте Bellman–Ford (для одного источника) или Johnson/Floyd–Warshall (для всех пар); SPFA — практическая оптимизация с оговорками.