Алгоритм Джонсона: различия между версиями

Версия от 08:18, 5 июля 2022

Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
Запустим алгоритм Форда-Беллмана из вершины s.
Зададим новые веса для всех рёбер: 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), что лучше, чем у алгоритма Флойда.

@@ Строка 1: / Строка 1: @@
+== Идея ==
 * Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
 * Запустим алгоритм Форда-Беллмана из вершины s.
-* Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + dist[v] - dist[to].
+* Зададим новые веса для всех рёбер: 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<sup>3</sup>) или O(VElogV).
+Если граф разреженный (E ~ V) и используется разреженный вариант Дейкстры, то общая сложность составит O(V<sup>2</sup>logV), что лучше, чем у алгоритма Флойда.
 == Ссылки ==