Алгоритм Джонсона

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск
  • Добавим в граф фиктивную вершину s, из которой во все остальные вершины идут рёбра нулевого веса.
  • Запустим алгоритм Форда-Беллмана из вершины s.
  • Зададим новые веса для всех рёбер: w'(v, to) = w(v, to) + dist[v] - dist[to].
  • Утверждается, что новые веса неотрицательны, а кратчайшие пути остались теми же; это позволяет запустить из каждой вершины алгоритм Дейкстры.

Ссылки