147
правок
Изменения
м
Нет описания правки
'''for''' <tex>(v \in V)</tex>
'''for''' <tex>(u : vu \; \in E)</tex>
<tex>d[k+1][u] \gets \min(d[k][u], \; d[k][v] + \omega(u,vuv))</tex>
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
:<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(v,uvu))</tex>
==Корректность==
: '''Индукционный переход.'''
::Сначала докажем, что <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(u,vuv)</tex> то есть вес любого найденного пути не меньше, чем <tex>\rho(s, v)</tex>, что неверно, следовательно неравенство выполняется.
