Алгоритм Джонсона: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 6: | Строка 6: | ||
== Ссылки == | == Ссылки == | ||
* [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 — Алгоритм Джонсона] | * [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 — Алгоритм Джонсона] | ||
* [http://brilliant.org/wiki/johnsons-algorithm Brilliant.org — Johnson's Algorithm] | |||
[[Category:Кратчайшие пути между всеми парами вершин]] | [[Category:Кратчайшие пути между всеми парами вершин]] | ||
Версия от 18:42, 2 января 2020
- Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
- Запустим алгоритм Форда-Беллмана из вершины s.
- Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + dist[v] - dist[to].
- Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры.