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