35
правок
Изменения
→Корректность алгоритма Форда-Беллмана
: Будем вести доказательство по индукцииДокажем следующее утверждение:: Перед первой фазой кратчайший путь до вершины : После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex> найден корректно: Воспользуемся индукцией по <tex>n</tex>:: '''База индукции. ''' Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] = d[s] = \delta(s, s) = 0</tex>: '''Индукционный переход.''' Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время первой фазы <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_0v_n, v_1v_{n+1})</tex> было просмотрено алгоритмом Форда-Беллмана, следовательно, расстояние до вершины по завершению итерации будет выполнено::<tex>v_1d[v_{n+1}] \le d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex> было корректно посчитано после первой фазы.: Повторяя эти утверждения Ясно, что <tex>kd[v_{n+1}] \ge \delta(s, v_{n+1}) </tex> раз, получаем, поэтому верно что после <tex>kl + 1</tex>-й фазы расстояние до вершины итерации <tex>vd[v_{n+1}] = \delta(s, v_{n + 1})</tex> посчитано корректно, что и требовалось доказать. : Индукционный переход доказан.
:Поэтому Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.<br>
}}
:Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>.<br>
:Просуммируем эти неравенства по всему циклу: <tex>\sum\limits_{i=1}^{k} {d[v_{i}]} \leqslant \sum\limits_{i=1}^{k} {d[v_{i-1}]} + \sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>.<br>
:Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.
