Алгоритм Джонсона: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
== TLDR == | |||
* Запустим алгоритм Форда-Беллмана из | <youtube width="300" height="180">8JQ565Rz7d8</youtube> | ||
* Зададим новые веса для всех рёбер: w'(v, to) = w(v, 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), что лучше, чем у алгоритма Флойда. | |||
== Ссылки == | == Ссылки == | ||
Текущая версия от 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), что лучше, чем у алгоритма Флойда.