1632
правки
Изменения
м
rollbackEdits.php mass rollback
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
Такая потенциальная функция строится при помощи добавлении добавлем фиктивной вершины <tex> s </tex> в <tex> G </tex>, из которой проведены ориентированные ребра нулевого веса во все остальные вершины графа, и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] из нее(<tex> \varphi(v) </tex> будет равно длине кратчайшего пути из <tex> s </tex> в <tex> v </tex>). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
