1632
правки
Изменения
м
Сначала стоит вспомнить формулу для количества Количество путей длины <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>.
::<tex>\vartriangleleft</tex>
'''Neg_Cycleint[]''' negativeCycle(G, s)''':''' '''for''' для каждой <tex>v \in V</tex> <tex> d[v] \leftarrow = <tex>\mathcal {1} </tex> <tex> p[v] \leftarrow = -1 </tex> <tex> d[s] \leftarrow = 0 </tex> '''for''' <tex> i \leftarrow = 1 </tex> '''to''' <tex>|V| - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v) </tex> '''then''' <tex> d[v] \leftarrow = d[u] + <tex>\omega(u, v)</tex> <tex> p[v] \leftarrow p[= u]</tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v)</tex> '''then''' '''for''' <tex> i \leftarrow 1 </tex> = 0 '''to''' <tex>|V| - 1 </tex> <tex> v \leftarrow = p[v]</tex> <tex> u \leftarrow = v</tex> '''while''' <tex> u \neq != p[v]</tex> <tex> ans.add(v) <font color="green">/tex/ добавим вершину к ответу</font> <tex> v \leftarrow = p[v]</tex> <tex> reverse(ans)</tex> '''break''' '''return''' <tex> ans </tex>
rollbackEdits.php mass rollback
{{Задача|definition==Алгоритм==Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <tex>G = (V, E)</tex> алгоритм находит найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.В, случае, когда в графе <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>, то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</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> — стартовая вершина.
Тогда после завершения <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> \rho(s, u) \leqslant d'[u]</tex>.
:Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..nk-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><br>
::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</tex>
:2 случай расписывается аналогично.
==Реализация алгоритма и ее корректность==
'''Bellman_Fordbool''' fordBellman(G, s)''':''' '''for''' для каждой <tex>v \in V</tex> <tex> d[v] \leftarrow = <tex>\mathcal {1} </tex> <tex> d[s] \leftarrow = 0 </tex> '''for''' <tex> i \leftarrow 1 </tex> = 0 '''to''' <tex> |V| - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v) </tex> '''then''' <font color="green">// <tex>\omega(u, v)</tex>{{---}} вес ребра uv</font> d[v] \leftarrow = d[u] + <tex>\omega(u, v)</tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v) </tex> '''thenreturn''' ''false'return' '' <tex> \mathit false</tex> 'return''return''' <tex> \mathit true </tex>''
В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>.
<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> — {{---}} стартовая вершина. Тогда после завершения <tex> |V| - 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>. Путь <tex> p </tex> содержит не более <tex> |V| - 1 </tex> ребер. Поэтому <tex>k \le leqslant |V| - 1</tex>.
Докажем следующее утверждение:
:После <tex>n : (n \le leqslant k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
Воспользуемся индукцией по <tex>n</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 leqslant 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 geqslant \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.
:Индукционный переход доказан.
{{Теорема
|statement=Пусть <tex>G = (V, E) </tex> {{- --}} взвешенный ориентированный граф, <tex> s </tex> — {{---}} стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V \ d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>.
|proof=Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </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>|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>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
== Источники информации ==:* Томас Х. Кормен, ТЧарльз И., Лейзерсон, ЧРональд Л., Ривест, Р., Клиффорд Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е изд — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.:* [http://e-maxx.ru/algo/export_ford_bellman ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]
