Решение: алгоритм Беллмана—Форда.
Алгоритм (кратко)
- Инициализация: для всех вершин $v$ положить $d[v]=\infty$, $d[s]=0$ (источник $s$).
- Повторить $V-1$ раз: для каждой дуги $(u\to v)$ с весом $w(u,v)$ выполнить релаксацию
если $d[u]+w(u,v)<d[v]$, то присвоить $d[v]=d[u]+w(u,v)$.
- Проверка отрицательного цикла: если после ещё одной итерации найдётся дуга с $d[u]+w(u,v)<d[v]$, то существует достижимый от $s$ отрицательный цикл.
Обоснование корректности
- Любой кратчайший путь без циклов содержит не более $V-1$ ребра. После $k$-й итерации алгоритма корректно вычислены длины всех кратчайших путей, состоящих не более чем из $k$ ребер. Поэтому после $V-1$ итераций получаем финальные кратчайшие расстояния при отсутствии отрицательных циклов.
- Проверка дополнительной релаксации обнаруживает отрицательный цикл, достижимый из $s$.
Сложность и память
- Временная сложность: $O(VE)$ (в худшем случае выполняется $V-1$ проход по всем $E$ дугам).
- Память: $O(V+E)$ для хранения графа и массива расстояний.
Оптимизации и альтернативы
- Ранний выход: если в проходе не было ни одного обновления, можно прервать раньше — это улучшает время на многих реальных графах.
- SPFA (очередь релаксаций) часто быстрее на практике, но не гарантирует лучшей границы в худшем случае и может деградировать (нестабильно для некоторых входов).
- Если граф ацикличен (DAG), тогда можно получить все кратчайшие пути за $O(V+E)$ с помощью топологической сортировки и одного прохода релаксаций.
- Если нужна многоточечная (all-pairs) задача, можно применить алгоритм Джонсона: сначала Bellman–Ford для потенциалов (удалить отрицательные веса), затем $V$ запусков Dijkstra — общая сложность $O(VE+V(E+V\log V))$ в зависимости от реализации.
Ограничения
- Беллман–Форд работает корректно при отрицательных весах, но медленнее, чем Dijkstra при неотрицательных весах.
- При больших плотных графах ($V$ и $E$ большие) временные затраты могут быть значительными.
- SPFA — практическая альтернатива, но с ненадёжными гарантиями в худшем случае.
Краткий вывод: для single-source в ориентированном графе с отрицательными весами и без отрицательных циклов рекомендован и обоснован алгоритм Беллмана—Форда (корректность и обнаружение отрицательных циклов, сложность $O(VE)$).