Изменения
→Нахождение отрицательного цикла
{{В разработке}}Задача|definition==Алгоритм==:Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <tex>G = (V, E)</tex> алгоритм находит найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>:В, случае, когда в графе <tex> G </tex> содержатся отрицательные [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|циклы]], достижимые из <tex> s</tex>, алгоритм сообщаетсообщить, что кратчайших путей не существует.}}
==Введение==
Аналогично посчитаем пути кратчайшей длины. Пусть <tex>s</tex> {{---}} стартовая вершина. Тогда <tex> d[k][u] = \min\limits_{v : vu \; \in E}(d[k-1][v] \: + \: \omega(u, v))</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> ребер, тогда корректность формулы следует из динамики, приведенной ниже.
}}
==Псевдокод==
'''for''' k = 0 '''to''' <tex>(k = 0 \; .. \; n|V| -2)</tex> <font color="green">// вершины нумеруются с единицы</font> '''for''' <tex>(v \in V)</tex> '''for''' <tex>(u : vu \; , v) \in E)</tex> <tex> d[k+1][uv] \gets \= min(d[k+ 1][uv], \; d[k][vu] + <tex>\omega(uvu, v)</tex>) <font color="green">// <tex>\omega(u, v)</tex> {{---}} вес ребра uv</font>
==Корректность==
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex>k</tex> итераций цикла <tex>\mathrm{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..k-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>
:Рассмотрим 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>
:2 случай расписывается аналогично.
}}
==Реализация алгоритма и ее корректность==
'''bool''' fordBellman(s)''':'''
'''for''' <tex>v \in V</tex>
d[v] = <tex>\mathcal {1}</tex>
d[s] = 0
'''for''' i = 0 '''to''' <tex> |V| - 1 </tex>
'''for''' <tex> (u, v) \in E </tex>
'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> <font color="green">// <tex>\omega(u, v)</tex> {{---}} вес ребра uv</font>
d[v] = d[u] + <tex>\omega(u, v)</tex>
'''for''' <tex> (u, v) \in E </tex>
'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex>
'''return''' ''false''
'''return''' ''true''
Докажем следующее утверждение:
:После <tex>n : (n \leqslant k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
Воспользуемся индукцией по <tex>n</tex>:
Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)</tex>.<br>
}}
Тогда если вершина <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> из несуществования пути.
После выполнения алгоритма верно, что для всех <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 </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </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> \Theta (V) </tex> времени, каждый из <tex> |V| - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Значит алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
Если после <tex>|V| - 1</tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>|V| - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>|V|</tex> вершин равна <tex>|V| - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле.
'''int[]''' negativeCycle(s)''':''' '''for''' <tex>v \in V</tex> d[v] =<tex>\mathcal {1}</tex> p[v] =Сложность-1 d[s] =0 '''for''' i =1 '''to''' <tex>|V| - 1</tex>:Инициализация занимает '''for''' <tex> \Theta (Vu, v) \in E </tex> времени, каждый из '''if''' d[v] > d[u] + <tex> \mid V \mid - 1 omega(u, v)</tex> проходов требует d[v] = d[u] + <tex> \Theta omega(Eu, v) </tex> времени p[v] = u '''for''' <tex> (u, обход по всем ребрам для проверки наличия отрицательного цикла занимает v) \in E </tex>O '''if''' d[v] > d[u] + <tex>\omega(Eu, v)</tex> времени. '''for''' i = 0 '''to''' <brtex>Итого алгоритм Беллмана|V| -Форда работает за 1</tex>O v = p[v] u = v '''while''' u != p[v] ans.add(V Ev) <font color="green">// добавим вершину к ответу</texfont> времени. v = p[v] reverse(ans) '''break''' '''return''' ans
== Источники информации ==:* Томас Х. Кормен, ТЧарльз И., Лейзерсон, ЧРональд Л., Ривест, Р., Клиффорд Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е изд — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.:* [http://e-maxx.ru/algo/export_ford_bellman ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]