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