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

Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин в ориентированном графе с положительными или отрицательными ребрами, но без отрицательных циклов.

Алгоритм

Сохранение кратчайших путей

Изменение веса

Псевдокод

Сложность

Алгоритм Джонсона работает за [math]O(VE + VD)[/math], где [math]O(D)[/math] - время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно [math]O(V^2\log V + V E)[/math].