147
правок
Изменения
Нет описания правки
: '''Индукционный переход.'''
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
::Предположим, что <tex>d'[u] + \omega(vu) \gtr geqslant \omega(Path(s \to v) \circ (vu))</tex>, то есть вес любого найденного пути больше чем <tex>\rho(s, u)</tex>/
<br>
}}
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. <br>
