147
правок
Изменения
м
Нет описания правки
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
::Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..n-1} d[i][u]</tex> для всех <tex>u</tex>.
::Тогда после <tex>k</tex> итераций <tex> \rho(s, v) = \min\limits_{u \ in V} (\rho(s, u) + \omega(uv)) \leqslant \min\limits_{u \in V} (d'[u] + \omega(uv)) = d'[v]</tex>.
