1
правка
Изменения
Нет описания правки
{{Задача
|definition=Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.
В случае, когда в графе <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[uv](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''' n <tex>|V| - 2</tex> <font color="green">// вершины нумеруются с единицы</font>
'''for''' <tex>v \in V</tex>
'''for''' <tex> (u, v) \in E </tex>
d[k + 1][uv] = min(d[k + 1][uv], d[k][vu] + <tex>\omega(u, v)</tex>) <font color="green">// <tex>\omega(u, v)</tex> {{--- }} вес ребра uv</font>
Также релаксацию можно свести к одномерному случаю (одномерный , если не хранить длину пути в рёбрах. Одномерный массив будем обозначать <tex>d'</tex>):, тогда <tex>d'[u] = \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>\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''' bellman_fordfordBellman(s)''':'''
'''for''' <tex>v \in V</tex>
d[v] = <tex>\mathcal {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> u </tex> лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
'''int[]''' neg_cyclenegativeCycle(s)''':'''
'''for''' <tex>v \in V</tex>
d[v] = <tex>\mathcal {1}</tex>
p[v] = -1
d[s] = 0
'''for''' i = 0 1 '''to''' <tex>|V| - 1</tex>
'''for''' <tex> (u, v) \in E </tex>
'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex>
'''return''' ans
== Источники информации ==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
* [http://e-maxx.ru/algo/ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана]
