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