81
правка
Изменения
→Теорема о существовании потенциальной функции
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>., введем потенциальную функцию <tex> \phi </tex>
:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)</tex>.
