147
правок
Изменения
м
Нет описания правки
{{Лемма
|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>,<br> то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex>
|proof=:Пусть кратчайший путь состоит из <tex>k</tex> ребер, тогда корректность формулы следует из динамики, приведенной ниже.<br>
}}
'''for''' <tex>(v \in V)</tex>
'''for''' <tex>(u : vu \; \in E)</tex>
<tex>d[k+1][u] \gets \min(d[k+ 1][u], \; d[k][v] + \omega(uv))</tex>
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
: '''Индукционный переход.'''
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
::Предположим, что Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \geqslant leqslant \min\rho(s,limits_{i=0..n-1} d[i][u)]</tex>, тогда для всех <tex> d'[u] + </tex>.::Тогда после <tex>k</tex> итераций <tex> \omegarho(uvs, v) = \min\limits_{u \geqslant in V} (\rho(s,u) + \omega(uv)</tex> то есть вес любого найденного пути не меньше, чем <tex>) \leqslant \min\limits_{u \in V} (d'[u] + \rhoomega(s, uv)) = d'[v)]</tex>, следовательно неравенство выполняется.
::Переходим ко второму неравенству, когда <tex>d'[u]</tex> изменилось.::<tex>d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex> выполняется, так как <tex>d'[u]</tex> могло только уменьшится, то это неравенство выполняется.
::Теперь возможно два случая:
::#<tex>\min\limits_{i = 0..k-+1} d[i][u] = d[k+1][u]</tex>::#<tex>\min\limits_{i = 0..k-+1} d[i][u] = d[j][u] = \min\limits_{i = 0..j} \; d[ji][u]</tex><br><br>
::Рассмотрим 1 случай:
:::<tex>\min\limits_{i = 0..k-+1} d[i][u] = d[k+1][u]</tex><br>
:::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</tex>
::<tex>\vartriangleleft</tex>
