Изменения

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

:Сначала стоит вспомнить формулу для количества Количество путей длины <tex>k</tex>рёбер можно найти с помощью метода [[Динамическое_программирование|динамического программирования]].<br>::Пусть <tex> d[k][u] = \sum\limits_</tex> {{v : vu \; \in E---}} d[количество путей длины <tex>k-1][v] </tex>:Теперь перепишем ее для пути кратчайшей длины. рёбер, заканчивающихся в вершине <tex>su</tex> {{---}} стартовая вершина.::Тогда <tex> d[k][u] = \minsum\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> ребер, тогда корректность формулы следует из динамики, приведенной ниже.

:Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.

'''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>

:Также релаксацию можно свести к одномерному случаю (одномерный , если не хранить длину пути в рёбрах. Одномерный массив будем обозначать <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>\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>\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> delta(us, v) \in E </tex>. '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then''' {{---}} оценка веса кратчайшего пути из вершины <tex>d[v] \leftarrow d[u] + \omega(u, v)s</tex> '''for''' для каждого ребра в каждую вершину <tex> (u, v) \in E V</tex>.<br> '''if''' <tex>d[v] > d[u] + \omegadelta(us, v) </tex> '''then''' '''return''' {{---}} фактический вес кратчайшего пути из <tex> \mathit falses</tex> '''return''' в вершину <tex> \mathit true v</tex>.

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

{{Лемма'''База индукции'''|statement:Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] =d[s] = \delta(s, s) = 0</tex>'''Индукционный переход''':Пусть после <tex>n : (n < k)</tex>G итераций, верно что <tex>d[v_n] = \delta(Vs, Ev_n) </tex> — взвешенный ориентированный граф. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex> s </tex> — стартовая вершина.до <brtex>Тогда после завершения v</tex>, то <tex> \mid V delta(s, v_{n+1}) = \delta(s, v_n) + \mid - omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1 </tex> итераций цикла для всех вершин, достижимых из итерации релаксируется ребро <tex>s(v_n,v_{n+1})</tex>, выполняется равенство следовательно по завершению итерации будет выполнено::<tex> d[vv_{n+1}] \leqslant d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta (s, vv_{n+1}) </tex>.|proof=:Рассмотрим произвольную вершину Ясно, что <tex>vd[v_{n+1}] \geqslant \delta(s, v_{n+1}) </tex>, достижимую из поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>. :Индукционный переход доказан.

:{{Теорема|statement=Пусть <tex>p G = \langle v_0(V,...E) </tex> {{---}} взвешенный ориентированный граф, v_<tex> s </tex> {{k---}} \rangle стартовая вершина. Если граф <tex> G </tex>не содержит отрицательных циклов, где достижимых из вершины <tex>v_0 = s</tex>, то алгоритм возвращает <tex>v_{k} = vtrue </tex> — кратчайший ациклический путь из и для всех <tex> v \in V \ d[v] = \delta (s , v)</tex> в . Если граф <tex> v G </tex>.содержит отрицательные циклы, достижимые из вершины <tex> s <br/tex>:Путь , то алгоритм возвращает <tex> p false </tex> содержит не более .|proof=Пусть граф <tex> \mid V \mid - 1 G </tex> ребер. Поэтому не содержит отрицательных циклов, достижимых из вершины <tex>k \le \mid V \mid - 1s </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})true </tex>. : Индукционный переход доказан.

: Итак, выполнены равенства Пусть граф <tex> G </tex> содержит отрицательный цикл <tex>d[v] c = d[{v_0,...,v_{k}] } </tex>, где <tex> v_0 = \delta (s, v_{k}) </tex>, достижимый из вершины <tex> s </tex>. Тогда <tex>\sum\limits_{i= 1}^{k} {\delta omega (sv_{i-1}, vv_{i})} < 0 </tex>.<br>}}

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

:Теперь докажемПолучили, что алгоритм вернет значение <tex> true </tex>.<br>:После выполнения алгоритма верно, что для всех <tex> (u, v) \in E, sum \ d[v] limits_{i= \delta (s, v) \leqslant \delta (s, u) + 1}^{k} {\omega (uv_{i-1},vv_{i}) = d[u] + } \omega (u,v)geqslant 0 </tex>, значит ни одна из проверок не вернет значения что противоречит отрицательности цикла <tex> false c </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 u </tex>лежит на цикле отрицательного веса, что противоречит отрицательности цикла можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина <tex> c 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 :: Алгоритм Форда-Беллмана]