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>). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G</tex>
:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) - + \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0</tex>
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
