Изменения

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

В алгоритме Джонсона используется [[алгоритм Беллмана — Форда]] и [[алгоритм Дейкстры]]. Алгоритм возврашает обычную матрицу <tex>D = d_{ij}</tex> размером <tex>|V|\times |V|</tex>, где <tex>d_{ij} = \delta(i,\;j)</tex>, или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.