Изменения

Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм ДейктсрыДейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.