Алгоритм Джонсона

Идея

• Запустим алгоритм Форда-Беллмана одновременно из всех вершин (для этого достаточно изначально заполнить массив расстояний нулями).
• Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + fordBellmanDist[v] - fordBellmanDist[to].
• Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры.
• Восстановим длины кратчайших путей: dist[a][b] = dijkstraDist[a][b] - fordBellmanDist[a] + fordBellmanDist[b].

Сложность

Запуск Форда-Беллмана — O(VE), V запусков Дейкстры — O(V³) или O(VElogV).

Если граф разреженный (E ~ V) и используется разреженный вариант Дейкстры, то общая сложность составит O(V²logV), что лучше, чем у алгоритма Флойда.

Ссылки

• neerc.ifmo.ru/wiki — Алгоритм Джонсона
• Brilliant.org — Johnson's Algorithm