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

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

Ссылки

• neerc.ifmo.ru/wiki — Алгоритм Джонсона