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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «* Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулев…»)
 
Нет описания правки
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
* Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
== TLDR ==
* Запустим алгоритм Форда-Беллмана из вершины s.
<youtube width="300" height="180">8JQ565Rz7d8</youtube>
* Зададим новые веса для всех рёбер: w'(u; v) = w(u; v) + dist(s, u) - dist(s, v).
 
== Идея ==
* Запустим алгоритм Форда-Беллмана одновременно из всех вершин (для этого достаточно изначально заполнить массив расстояний нулями).
* Зададим новые веса для всех рёбер: 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), что лучше, чем у алгоритма Флойда.


== Ссылки ==
== Ссылки ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Джонсона]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Джонсона]
* [http://brilliant.org/wiki/johnsons-algorithm Brilliant.org — Johnson's Algorithm]


[[Category:Кратчайшие пути между всеми парами вершин]]
[[Category:Кратчайшие пути между всеми парами вершин]]

Текущая версия от 15:30, 24 мая 2023

TLDR

Идея

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

Сложность

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

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

Ссылки