35
правок
Изменения
→Описание
=== Описание ===
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2 * \log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асиптотически асимптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{\omega} </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится при помощи так называемой '''потенциальной''' функции.
{{Определение
|definition=
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> - произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \hat{omega_\omega}varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
}}
