==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>:В, случае, когда в графе <tex> G </tex> содержатся отрицательные циклы, достижимые из <tex> s</tex>, алгоритм сообщает, что кратчайших путей не существует.
==Введение==
:Сначала стоит вспомнить формулу для количества путей длины <tex>k</tex>.::<tex> d[k][u] = \sum\limits_{v : vu \; \in E} d[k-1][v] </tex>:Теперь перепишем ее для пути кратчайшей длины. <tex>s</tex> {{---}} стартовая вершина.::<tex> d[k][u] = \min\limits_{v : vu \; \in E}(d[k-1][v] \: + \: \omega[uv])</tex>, при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\infty </tex>
{{Лемма
|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>,<br> то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex>|proof=:Пусть кратчайший путь состоит из <tex>k</tex> ребер, тогда корректность формулы следует из динамики, приведенной ниже.<br>
}}
==Псевдокод==
:Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' <tex>(k = 0 \; .. \; n-2)</tex>
'''for''' <tex>(v \in V)</tex> '''for''' <tex>(u : vu \; \in E)</tex> <tex>d[k+1][u] \gets \min(d[k + 1][u], \; d[k][v] + \omega(uv))</tex>
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>)::<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(vu))</tex>
==Корректность==
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex>k</tex> итераций цикла <tex>for(k)</tex> выполняется неравенство <tex> \rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex>.|proof=: Воспользуемся индукцией по <tex>k</tex>:
: '''База индукции.''' :При <tex>k = 0</tex> выполнено: <tex>\rho(s, u) \leqslant +\infty \leqslant +\infty </tex>: '''Индукционный переход.'''::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.::Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..n-1} d[i][u]</tex> для всех <tex>u</tex>.::Тогда после <tex>k</tex> итераций <tex> \rho(s, v) = \min\limits_{u \in V} (\rho(s, u) + \omega(uv)) \leqslant \min\limits_{u \in V} (d'[u] + \omega(uv)) = d'[v]</tex>.
'''Индукционный переход'''
:Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
:Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..n-1} d[i][u]</tex> для всех <tex>u</tex>.
:Тогда после <tex>k</tex> итераций <tex> \rho(s, v) = \min\limits_{u \in V} (\rho(s, u) + \omega(uv)) \leqslant \min\limits_{u \in V} (d'[u] + \omega(uv)) = d'[v]</tex>.
::Переходим ко второму неравенству.
::Теперь возможно два случая:
::#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex>
::#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[j][u] =\min\limits_{i = 0..j} \; d[i][u]</tex>
:Переходим ко второму неравенству.
:Теперь возможно два случая:
:#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex>
:#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[j][u] =\min\limits_{i = 0..j} \; d[i][u]</tex>
::Рассмотрим 1 случай::::<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex><br>:::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</tex>
::<tex>\vartriangleleft</tex>
::2 случай расписывается аналогично.
:Таким образом переход выполнен и <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex> выполняется.<br>
}}
==Реализация алгоритма и ее корректность==
'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V</tex> <tex> d[v] \leftarrow \mathcal {1} </tex> <tex>d[s] \leftarrow 0 </tex> '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid |V \mid | - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then''' '''return''' <tex> \mathit false</tex> '''return''' <tex> \mathit true </tex>
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. <br>:<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br>:<tex>\delta(s, v)</tex> - фактический вес кратчайшего пути из <tex>s</tex> в вершину <tex>v</tex>.
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex> \mid |V \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 \mid | - 1 </tex> ребер. Поэтому <tex>k \le \mid |V \mid | - 1</tex>.
Докажем следующее утверждение:
:После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
Воспользуемся индукцией по <tex>n</tex>:
: Докажем следующее утверждение: :: После <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_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
::<tex>d[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>d[v_{n+1}] \ge \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>. : Индукционный переход доказан.
Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)</tex>.<br>
}}
: Итак{{Теорема|statement=Пусть <tex>G = (V, выполнены равенства E) </tex>- взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V \ d[v] = d[v_{k}] = \delta (s, v_{k}v) = \delta (</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s</tex>, v)то алгоритм возвращает <tex> false </tex>.|proof=Пусть граф <tex> G <br/tex>}}не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>.
Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути.
{{Теорема|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>Теперь докажем, то что алгоритм возвращает вернет значение <tex> true </tex> и для всех <tex> v \in V \ 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> (u, v) \in E, \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.
:Теперь докажем, что алгоритм вернет значение Пусть граф <tex> true G </tex>содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} <br/tex>:После выполнения алгоритма верно, что для всех где <tex> v_0 = v_{k} </tex> (u, v) \in E, \ d[v] = \delta (достижимый из вершины <tex> s, v) </tex>. Тогда <tex>\leqslant sum\delta (s, u) + \omega (u,v) limits_{i= d[u] + 1}^{k} {\omega (uv_{i-1},vv_{i})} </tex>, значит ни одна из проверок не вернет значения <tex> false 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> 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> 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 \mid | - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого Значит алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
==Нахождение отрицательного цикла==
:Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно сохранять массив вершин запоминать вершины, из которых производится релаксация. Тогда, если после <tex> \mid |V \mid | - 1 </tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>\mid |V \mid | - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>\mid |V \mid|</tex> вершин равна <tex>\mid |V \mid | - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле. Теперь, зная что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно пройти из нее по предкам, пока не придем в ту же вершину <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
'''Neg_Cycle(G, s)'''
<tex> p[v] \leftarrow -1 </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid |V \mid | - 1 </tex>
'''for''' для каждого ребра <tex> (u, v) \in E </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then'''
'''for''' для каждого ребра <tex> (u, v) \in E </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v)</tex> '''then'''
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid |V \mid | - 1 </tex>
<tex>v \leftarrow p[v]</tex>
<tex>u \leftarrow v</tex>
