Кратко — алгоритмы и когда применять.
1) Bellman–Ford (один источник, допускает отриц. ребра, требование: нет отриц. циклов)
- Идея: инициализировать $d(s)=0$, остальные $d(v)=+\infty$; повторно «релаксировать» все ребра ровно $|V|-1$ раз. После этого расстояния корректны; дополнительная итерация детектирует отриц. цикл, если какие‑то $d$ изменились.
- Псевдокод (сжато): для $i=1$ до $|V|-1$: для каждого ребра $(u,v)$ если $d(u)+w(u,v)<d(v)$ то $d(v)=d(u)+w(u,v)$. После: ещё одна итерация — если есть улучшение, то есть отриц. цикл.
- Сложность: $\mathcal{O}(|V|\cdot |E|)$ по времени, $\mathcal{O}(|V|+|E|)$ по памяти.
- Применимость: надежен для single‑source в графах с отриц. ребрами; обнаруживает отриц. циклы.
2) Dijkstra напрямую — нельзя, если есть отриц. ребра (жадность нарушается).
- Пример провала: наличие отрицательного ребра может сделать уже «закрытое» расстояние улучшенным через более длинный путь.
3) Johnson (переход к неотрицательным весам) — когда нужно all‑pairs или хочется использовать Dijkstra после пересчёта
- Шаги:
1. Добавить вспомогательную вершину $s^{\prime }$ со сведениями $w(s^{\prime },v)=0$ для всех $v$.
2. Запустить Bellman–Ford от $s^{\prime }$ и получить потенциалы $h(v)=\delta (s^{\prime },v)$. Если найден отриц. цикл — останов.
3. Переопределить веса: $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)$. Тогда все $w^{\prime }\ge 0$.
4. Для каждого источника $s$ запустить Dijkstra с весами $w^{\prime }$, получив $d^{\prime }(v)$. Восстановить оригинальные расстояния: $d(v)=d^{\prime }(v)-h(s)+h(v)$.
- Сложность: Bellman–Ford $\mathcal{O}(|V|\cdot |E|)$ + для каждого источника Dijkstra (с кучей) $\mathcal{O}(|E|+|V|\log |V|)$. Для all‑pairs итог: $\mathcal{O}(|V|\cdot |E|+|V{|}^2\log |V|)$ (на практике: $\mathcal{O}(|V|\cdot |E|+|V|\cdot (|E|+|V|\log |V|))$).
- Применимость: эффективно для all‑pairs в разреженных графах; для single‑source обычно проще Bellman–Ford (если нет других причин).
4) SPFA (очередь релаксаций) — практический эвристический вариант Bellman–Ford
- Часто быстрее на реальных данных, но в худшем случае $\mathcal{O}(|V|\cdot |E|)$ (и в некоторых конструкциях — крайне плохой) — использовать осторожно.
Рекомендации выбора
- Single‑source + отриц. рёбра (и нужно детектировать отриц. цикл) — Bellman–Ford.
- All‑pairs + отриц. рёбра (нет отриц. циклов) — Johnson (BF для потенциалов + Dijkstra для каждого источника).
- Нет отриц. рёбер — Dijkstra.
- Практическая альтернатива для Single‑source: SPFA (быстро обычно, но не гарантированно).
Короткое обоснование корректности Bellman–Ford: кратчайший простой путь содержит не более $|V|-1$ рёбер, поэтому после $|V|-1$ полных проходов по всем рёбрам все такие пути будут учтены; дополнительная итерация показывает наличие отриц. цикла.