Алгоритм Джонсона: Кратчайшие пути между всеми парами вершин

Очевидная идея для ускорения: почему бы просто не запустить быстрый алгоритм Дейкстры от каждой вершины? Если мы запустим Дейкстру V раз (с использованием Фибоначчиевой кучи), мы получим искомую сложность O(V^2 log V + VE). Но есть фундаментальная проблема: алгоритм Дейкстры математически ломается, если в графе присутствуют ребра с отрицательным весом.

Дональд Джонсон придумал, как изменить веса всех ребер графа так, чтобы они стали строго положительными, но при этом истинные кратчайшие пути остались кратчайшими! (Просто прибавить ко всем ребрам одно большое число нельзя, так как пути, состоящие из большего количества ребер, неоправданно подорожают).

Алгоритм использует концепцию перевзвешивания графа с помощью потенциалов:

1. В граф добавляется новая фиктивная "супервершина" S, соединенная со всеми остальными вершинами ребрами с весом 0.
2. Из вершины S запускается алгоритм Беллмана-Форда (который умеет работать с отрицательными весами). Он находит минимальные расстояния h(v) от S до всех вершин v. Эти числа h(v) становятся математическими "потенциалами" вершин. (Если Беллман-Форд находит отрицательный цикл, алгоритм прерывается — путей не существует).
3. Магия перевзвешивания: вес каждого ребра от u к v изменяется по формуле: w'(u, v) = w(u, v) + h(u) - h(v). Математика гарантирует (неравенство треугольника из Беллмана-Форда), что новые веса w' всегда будут больше или равны нулю! При этом любой путь между узлами X и Y изменится на константу h(X) - h(Y), независимо от количества промежуточных вершин. Кратчайшие пути не искажаются.
4. Супервершина удаляется. Теперь, когда все ребра стали положительными, алгоритм V раз запускает Дейкстру.
5. В конце из найденных расстояний просто вычитается разница потенциалов h(X) - h(Y), возвращая реальные длины маршрутов.

Алгоритм Джонсона — это эталон того, как глубокое понимание алгебраических инвариантов позволяет программистам манипулировать данными, открывая доступ к сверхбыстрым методам обработки там, где они изначально казались неприменимыми.