Изменения

{{Задача|definition==Алгоритм==:Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <tex>G = (V, E)</tex> алгоритм находит найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>:В случае , когда в графе <tex> G </tex> содержатся отрицательные [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|циклы ]] с отрицательным суммарным весом, достижимые из <tex> s </tex> алгоритм сообщает, сообщить, что кратчайших путей не существует.}} ==Введение==Количество путей длины <tex>k</tex> рёбер можно найти с помощью метода [[Динамическое_программирование|динамического программирования]]. <br>Пусть <tex>d[k][u]</tex> {{---}} количество путей длины <tex>k</tex> рёбер, заканчивающихся в вершине <tex>u</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(u, v))</tex>, при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\infty </tex>{{Лемма|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>, то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex>|proof=Пусть кратчайший путь состоит из <tex>k</tex> ребер, тогда корректность формулы следует из динамики, приведенной ниже.}}

'''Bellman_Ford(G, s)for''' k = 0 '''forto''' для каждой <tex>v \in |V[G]| - 2</tex> <texfont color="green"> d[v] \leftarrow \mathcal {1} </tex> <tex>d[s] \leftarrow 0 / вершины нумеруются с единицы</texfont> '''for''' <tex> i v \leftarrow 1 </tex> '''to''' <tex> \mid in V[G] \mid - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E[G] </tex> '''if''' <tex> d[k + 1][v] > = min(d[uk + 1][v] + \omega(u, v) </tex> '''then''' <tex>d[vk] \leftarrow d[u] + <tex>\omega(u, v)</tex> '''for''' для каждого ребра ) <texfont color="green"> (u, v) \in E[G] </tex> '''if''' / <tex>d[v] > d[u] + \omega(u, v) </tex> '''then''' '''return''' <tex> \mathit false</tex> '''return''' <tex> \mathit true {{---}} вес ребра uv</texfont>

==Корректность алгоритма Форда-Беллмана==:В этом алгоритме используется релаксацияТакже релаксацию можно свести к одномерному случаю, если не хранить длину пути в результате которой рёбрах. Одномерный массив будем обозначать <tex>d[v]'</tex> уменьшается до тех пор, пока не станет равным тогда <tex>d'[u] = \deltamin(sd'[u], v)</tex>. <br>:<tex>\; d'[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br>:<tex>+ \deltaomega(s, vvu))</tex> - фактический вес кратчайшего пути из <tex>s</tex> в вершину <tex>v</tex>.

|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex> \mid V[G] \mid - 1 k</tex> итераций цикла для всех вершин, достижимых из <tex>s\mathrm{for}</tex>, выполняется равенство неравенство <tex> d[v] = \delta rho(s, vu) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex>.|proof=:Рассмотрим произвольную вершину Воспользуемся индукцией по <tex>vk</tex>, достижимую из <tex>s</tex>.:

'''Индукционный переход''':Пусть Сначала докажем, что <tex>p = \langle v_0,...rho(s, v_{k} u) \rangle leqslant d'[u]</tex>, где .:Пусть после <tex>v_0 = sk - 1 </tex>, итерации выполняется <tex>v_\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..k-1} = v</tex> — кратчайший ациклический путь из <tex> s d[i][u]</tex> в для всех <tex> v u</tex>.<br>:Путь Тогда после <tex> p k</tex> содержит не более итераций <tex> \mid rho(s, v) = \min\limits_{u \in V[G] } (\rho(s, u) + \omega(uv)) \leqslant \mid - 1 </tex> ребер. Поэтому <tex>k min\le limits_{u \mid in V} (d'[Gu] + \mid - 1omega(uv)) = d'[v]</tex>.

:На каждой из Переходим ко второму неравенству.:Теперь возможно два случая::#<tex> \mid Vmin\limits_{i = 0..k+1} d[i][Gu] \mid - = d[k+1 </tex> итераций цикла <b> for </b> релаксируются <tex> \mid E][Gu] \mid </tex> ребер.<br>:Среди ребер, прорелаксированных во время i-й итерации, находится ребро #<tex> (v_\min\limits_{i-= 0..k+1}, v_d[i][u] = d[j][u] =\min\limits_{i= 0..j}) \; d[i][u]</tex>.

 :Рассмотрим 1 случай:::Поэтому выполнены равенства <tex>\min\limits_{i = 0..k+1} d[vi][u] = d[v_{k}+1][u]</tex><br>::<tex>d'[u] \leqslant d'[v] = + \delta omega(s, v_{vu) \leqslant d[k}][v] + \omega(vu) = d[k+1][u]</tex>:2 случай расписывается аналогично. Таким образом переход выполнен и <tex>\delta rho(s, v)u)\leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</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} {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>. Из того, что <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 geqslant 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> времени. ==Нахождение отрицательного цикла==Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно хранить вершины, из которых производится релаксация.  Если после <tex>|V| - 1</tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>|V| - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>|V|</tex> вершин равна <tex>|V| - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле.  Зная, что вершина <tex> u </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> (u, v) \in E </tex> '''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> d[v] = d[u] + <tex>\omega(u, v)</tex> p[v] = u '''for''' <tex> (u, v) \in E </tex> '''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> '''for''' i = 0 '''to''' <tex>|V| - 1</tex> v = p[v] u = v '''while''' u != p[v] ans.add(v) <font color="green">// добавим вершину к ответу</font> v = p[v] reverse(ans) '''break''' '''return''' ans

== Литература Источники информации ==:* Томас Х. Кормен, ТЧарльз И., Лейзерсон, ЧРональд Л., Ривест, Р., Клиффорд Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е изд — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.* [http://e-maxx.ru/algo/ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана]