Изменения

Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. Тогда <tex>\sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>. Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>. Просуммируем эти неравенства по всему циклу: <tex>\sum_{i=1}^{k} {d[v_{i}]} \leqslant \sum_{i=1}^{k} {d[v_{i-1}]} + \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>. Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum^{k}_{i=1} {d[v_{i}]} = \sum_{i=1}^{k} {d[v_{i - 1}]} </tex>. Получили, что <tex> \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} >= 0 </tex>, что противоречит отрицательности цикла <tex> c </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> времени.