Изменения

:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин, в .<br>:В случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.

'''do''' '''for''' для каждого ребра <tex> (u, v) \in E[G] </tex> '''do''' '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>

'''do''' '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>

|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. <br>Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.|proof=:Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>, .  :Пусть <tex>p = {\langle v_0,..., v_{k}}\rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. <br>:Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. Поэтому <tex>k \le \mid V[G] \mid - 1</tex>.  :На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла <b> for </b> релаксируются <tex> \mid E[G] \mid </tex> ребер. <br>:Среди ребер, прорелаксированных во время i-й итерации, находится ребро <tex> (v_{i-1}, v_{i}) </tex>.  :Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.

|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. <br>Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V[G] \ d[v] = \delta (s, v)</tex>. <br>Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>|proof=:Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. <br>:Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. <br>:Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути.   :Теперь докажем, что алгоритм вернет значение <tex> true </tex>. <br>:После выполнения алгоритма верно, что для всех <tex> (u, v) \in E[G], \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.  :Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. <br>:Тогда <tex>\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </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>.   :Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.

:Инициализация занимает <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.