Алгоритм Джонсона: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «* Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулев…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
* Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса. | * Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса. | ||
* Запустим алгоритм Форда-Беллмана из вершины s. | * Запустим алгоритм Форда-Беллмана из вершины s. | ||
* Зададим новые веса для всех рёбер: w'( | * Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + dist[v] - dist[to]. | ||
* Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры. | * Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры. | ||
Версия от 18:10, 28 сентября 2019
- Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
- Запустим алгоритм Форда-Беллмана из вершины s.
- Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + dist[v] - dist[to].
- Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры.