147
правок
Изменения
Нет описания правки
:На каждой из Будем вести доказательство по индукции:: Перед первой фазой кратчайший путь до вершины <tex> \mid Vs</tex> найден корректно. <tex>d[Gs] \mid - 1 = 0</tex> итераций цикла : Во время первой фазы ребро <btex> for (v_0, v_1)</btex> релаксируются было просмотрено алгоритмом Форда-Беллмана, следовательно, расстояние до вершины <tex> \mid E[G] \mid v_1</tex> ребербыло корректно посчитано после первой фазы.: Повторяя эти утверждения <brtex>:Среди реберk</tex> раз, получаем, прорелаксированных во время iчто после <tex>k</tex>-й итерации, находится ребро фазы расстояние до вершины <tex> (v_{i-1}, v_{i}) v</tex>посчитано корректно, что и требовалось доказать.
:Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.<br>
}}
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
== Литература Источники ==
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
:[http://e-maxx.ru/algo/export_ford_bellman Алгоритм Форда-Беллмана]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]
