Кратко — почему неверно, демонстрация и корректные заменители.
Почему жадный Dijkstra ломается при отрицательных ребрах
- Ключевое свойство Dijkstra: если в очереди необработанных вершин вершина $u$ имеет минимальную текущую оценку $\mathrm{dist}[u]$, то эта оценка уже равна истинному кратчайшему расстоянию от источника. Это верно при неотрицательных весах, потому что любой путь, проходящий через ещё не обработанную вершину, не может уменьшить длину (ребро добавляет неотрицательное значение).
- При отрицательных ребрах это свойство нарушается: может существовать путь через ещё не обработанные вершины, который уменьшит $\mathrm{dist}[u]$.
Простой контрпример
- Граф: вершины $s,a,b$. Рёбра: $s\to a$ вес $0$, $s\to b$ вес $1$, $b\to a$ вес $-2$.
- Инициализация: $\mathrm{dist}[s]=0,\mathrm{dist}[a]=0,\mathrm{dist}[b]=1$.
- Dijkstra выберет минимальную необработанную вершину $a$ (значение $0$) и "зафиксирует" её. Но истинный кратчайший путь $s\to b\to a$ имеет длину $1+(-2)=-1<0$. После фиксации $a$ её значение не изменится — алгоритм даёт неверный результат.
Почему математически: при отрицательных ребрах условие монотонности нарушено — возможные улучшения через необработанные вершины не гарантированно не уменьшают текущие метки.
Корректные альтернативы и преобразования (кратко, с оценками сложности)
1) Bellman–Ford (одиночный источник, допускает отрицательные веса; обнаруживает отрицательные циклы)
- Описание: релаксировать все ребра до $V-1$ раз; затем дополнительный проход для обнаружения отрицательного цикла.
- Сложность: $O(VE)$.
- Применимость: одиночный источник, работает при любых весах (кроме случаев, когда интересна неограниченно малая длина из-за отрицательного цикла — тогда задача не имеет смысла).
2) SPFA (Shortest Path Faster Algorithm)
- Описание: оптимизация Bellman–Ford с очередью (релаксация только нужных ребер).
- Практика: часто быстрее на разреженных реальных графах.
- Сложность: в худшем случае асимптотика сравнима с Bellman–Ford ($O(VE)$), на специальных случаях может деградировать; не гарантированно лучше в теории.
- Применимость: практический выбор, но осторожно на анти-паттерн графах.
3) Алгоритм для DAG (если граф ацикличен)
- Описание: топологическая сортировка + однократная релаксация рёбер в порядке топологической сортировки.
- Сложность: $O(V+E)$.
- Применимость: подходит, если граф ориентированный и ацикличен; допускает отрицательные веса.
4) Johnson — все-пары кратчайших путей с переквотировкой (reweighting)
- Идея: добавить фиктивный источник $s^{\prime }$ с нулевыми рёбрами ко всем вершинам, запустить Bellman–Ford от $s^{\prime }$ и получить потенциалы $h(v)=\mathrm{dist}(s^{\prime },v)$. Затем переопределить веса
$$w^{\prime }(u,v)=w(u,v)+h(u)-h(v),$$ эти $w^{\prime }$ неотрицательны, и кратчайшие пути сохраняются по порядку. После этого запускать Dijkstra из каждой вершины по $w^{\prime }$ и переводить ответы обратно.
- Сложность: Bellman–Ford за $O(VE)$ + $V$ запусков Dijkstra. Итог (зависит от реализации Dijkstra):
- с Fibonacci-кучей: $O(VE+V^2\log V)$;
- с бинарной кучей: примерно $O(VE\log V)$ при доминировании $E$.
- Применимость: когда нужно найти все-пары кратчайшие пути в графе с отрицательными, но не циклически отрицательными весами.
5) Прямое исправление путём добавления константы ко всем рёбрам — НЕ корректно
- Если добавить постоянную $C$ к каждому весу, то длина пути с $k$ рёбрами изменится на $kC$. Порядок предпочтения путей может измениться (короткий по сумме может иметь больше/меньше рёбер), поэтому это не сохраняет корректность для всех пар вершин.
Дополнительные замечания
- Если в графе есть достижимый отрицательный цикл, коротчайшие пути (по сумме весов) не определены (можно сделать длину сколь угодно малой) — Bellman–Ford и SPFA умеют это обнаруживать.
- Если требуются кратчайшие пути от одного источника в общем графе с отрицательными весами — используйте Bellman–Ford (гарантия) или SPFA (практически быстрее, но с оговорками). Если требуется все-пары — Johnson предпочтителен (когда $V$ не слишком велик и $E$ разрежён) или квадратный алгоритм Floyd–Warshall ($O(V^3)$) как простой вариант (подходит при плотных графах и небольших $V$).
Резюме
- Приведённый псевдокод Dijkstra неверен при отрицательных рёбрах потому, что жадное утверждение о "финальности" минимальной текущей метки нарушается.
- Правильные методы: Bellman–Ford (S S P с отрицательными весами), SPFA (практическая оптимизация), алгоритм для DAG (если ацикличен), Johnson (для all-pairs с переквотировкой), Floyd–Warshall ($O(V^3)$) — выбор зависит от задачи и размеров графа.