Изменения
Нет описания правки
'''return''' <tex> \mathit true </tex>
==Корректность алгоритма Беллмана-Форда==
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> -взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из s выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=Рассмотрим произвольную вершину <tex> v </tex> достижимую из <tex> s </tex>, <tex> p = {v_0,..., v_{k}} </tex>, где <tex> v_0 = s </tex>, <tex> v_{k} = v </tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла релаксируются <tex> \mid E[G] \mid </tex> ребер. Среди ребер, прорелаксированных во время i-й итерации находится ребро <tex> (v_{i-1}, v_{i}) </tex>. Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>
}}
==Сложность==
Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex>|\mid V| [G] \mid - 1</tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
