147
правок
Изменения
Нет описания правки
{{В разработке}}
==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
:<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(v,u,v))</tex>
==Корректность==
: '''Индукционный переход.'''
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
::Предположим, что <tex>d'[u] \geqslant \rho(s,u)</tex>, тогда <tex>d'[u] + \omega(vuuv) \geqslant \omega(Pathrho(s \to v,u) + \circ omega(vu)u,v)</tex>, то есть вес любого найденного пути больше не меньше, чем <tex>\rho(s, uv)</tex>, что неверно, следовательно неравенство выполняется.
'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
<tex> d[v] \leftarrow \mathcal {1} </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V[G] \mid - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E[G] </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[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</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>.
{{Теорема
|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> 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> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
== Источники ==
