147
правок
Изменения
м
Нет описания правки
::<tex> d[k][u] = \sum\limits_{v : vu \; \in E} d[k-1][v] </tex>
:Теперь перепишем ее для пути кратчайшей длины. <tex>s</tex> {{---}} стартовая вершина.
::<tex> d[k][u] = \min\limits_{v : vu \; \in E}(d[k-1][v] \: + \: \omega[uv])</tex>, при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\inf infty </tex>
{{Лемма
|proof=: Воспользуемся индукцией по <tex>k</tex>:
: '''База индукции.''' При <tex>k = 0</tex> выполнено: <tex>\rho(s, u) \leqslant +\inf infty \leqslant +\inf infty </tex>
: '''Индукционный переход.'''
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
