205
правок
Изменения
→Сохранение кратчайших путей
=== Сохранение кратчайших путей ===
Пусть есть потенциальная функция: <tex>\phi: V \rightarrow \mathbb{R}, \; uv </tex> - ребро, тогда <tex> w_\phi(uv) = w(uv) + \phi(u) - \phi(v) </tex>
{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b.\; w(P) < w(Q)</tex>. Тогда <tex>\forall \phi: \; w_\phi(P) < w_\phi(Q)</tex>
|proof=
<tex>w_\phi(P) < w_\phi(Q)</tex>
<tex>w_\phi(P) = \phi(a) + w(P) - \phi(b)</tex>
<tex>w_\phi(Q) = \phi(a) + w(Q) - \phi(b)</tex>
Отсюда, <tex>w(P) < w(Q)</tex>
}}
=== Изменение веса ===
