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

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

Ссылки

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