Алгоритм Форда-Беллмана — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 9 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
{{Задача | {{Задача | ||
|definition=Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. | |definition=Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. | ||
− | В случае, когда в графе <tex>G</tex> содержатся | + | В случае, когда в графе <tex>G</tex> содержатся [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|циклы]] с отрицательным суммарным весом, достижимые из <tex>s</tex>, сообщить, что кратчайших путей не существует. |
}} | }} | ||
==Введение== | ==Введение== | ||
− | Количество путей длины <tex>k</tex> можно найти с помощью метода [[Динамическое_программирование|динамического программирования]]. <br> | + | Количество путей длины <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>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 | + | Аналогично посчитаем пути кратчайшей длины. Пусть <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> | |statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>, то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex> | ||
Строка 17: | Строка 17: | ||
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования. | Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования. | ||
− | '''for''' k = 0 '''to''' | + | '''for''' k = 0 '''to''' <tex>|V| - 2</tex> <font color="green">// вершины нумеруются с единицы</font> |
'''for''' <tex>v \in V</tex> | '''for''' <tex>v \in V</tex> | ||
'''for''' <tex> (u, v) \in E </tex> | '''for''' <tex> (u, v) \in E </tex> | ||
− | d[k + 1][ | + | d[k + 1][v] = min(d[k + 1][v], d[k][u] + <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> |
− | <tex>d'[u] = \min(d'[u], \; d'[v] + \omega(vu))</tex> | ||
==Корректность== | ==Корректность== | ||
Строка 29: | Строка 28: | ||
{{Лемма | {{Лемма | ||
|statement=Пусть <tex>G = (V, E)</tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. | |statement=Пусть <tex>G = (V, E)</tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. | ||
− | Тогда после завершения <tex>k</tex> итераций цикла <tex>\mathrm{for | + | Тогда после завершения <tex>k</tex> итераций цикла <tex>\mathrm{for}</tex> выполняется неравенство <tex> \rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex>. |
|proof=Воспользуемся индукцией по <tex>k</tex>: | |proof=Воспользуемся индукцией по <tex>k</tex>: | ||
Строка 50: | Строка 49: | ||
::<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex><br> | ::<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> | ::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</tex> | ||
− | |||
:2 случай расписывается аналогично. | :2 случай расписывается аналогично. | ||
Строка 57: | Строка 55: | ||
==Реализация алгоритма и ее корректность== | ==Реализация алгоритма и ее корректность== | ||
− | '''bool''' | + | '''bool''' fordBellman(s)''':''' |
'''for''' <tex>v \in V</tex> | '''for''' <tex>v \in V</tex> | ||
d[v] = <tex>\mathcal {1}</tex> | d[v] = <tex>\mathcal {1}</tex> | ||
Строка 97: | Строка 95: | ||
{{Теорема | {{Теорема | ||
− | |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>. | + | |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>. | |proof=Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. | ||
Строка 127: | Строка 125: | ||
Зная, что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу. | Зная, что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу. | ||
− | '''int[]''' | + | '''int[]''' negativeCycle(s)''':''' |
'''for''' <tex>v \in V</tex> | '''for''' <tex>v \in V</tex> | ||
d[v] = <tex>\mathcal {1}</tex> | d[v] = <tex>\mathcal {1}</tex> | ||
p[v] = -1 | p[v] = -1 | ||
d[s] = 0 | d[s] = 0 | ||
− | '''for''' i = | + | '''for''' i = 1 '''to''' <tex>|V| - 1</tex> |
'''for''' <tex> (u, v) \in E </tex> | '''for''' <tex> (u, v) \in E </tex> | ||
'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> | '''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> | ||
Строка 149: | Строка 147: | ||
'''return''' ans | '''return''' ans | ||
− | == Источники == | + | == Источники информации == |
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5. | * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5. | ||
* [http://e-maxx.ru/algo/ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана] | * [http://e-maxx.ru/algo/ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана] |
Текущая версия на 19:12, 4 сентября 2022
Задача: |
Для заданного взвешенного графа найти кратчайшие пути из заданной вершины до всех остальных вершин. В случае, когда в графе содержатся циклы с отрицательным суммарным весом, достижимые из , сообщить, что кратчайших путей не существует. |
Введение
Количество путей длины динамического программирования.
Пусть — количество путей длины рёбер, заканчивающихся в вершине . Тогда .
Аналогично посчитаем пути кратчайшей длины. Пусть
— стартовая вершина. Тогда , при этом , аЛемма: |
Если существует кратчайший путь от до , то |
Доказательство: |
Пусть кратчайший путь состоит из | ребер, тогда корректность формулы следует из динамики, приведенной ниже.
Псевдокод
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
for k = 0 to// вершины нумеруются с единицы for for d[k + 1][v] = min(d[k + 1][v], d[k][u] + ) // — вес ребра uv
Также релаксацию можно свести к одномерному случаю, если не хранить длину пути в рёбрах. Одномерный массив будем обозначать
, тогдаКорректность
Лемма: |
Пусть — взвешенный ориентированный граф, — стартовая вершина.
Тогда после завершения итераций цикла выполняется неравенство . |
Доказательство: |
Воспользуемся индукцией по :База индукции
Индукционный переход
|
Реализация алгоритма и ее корректность
bool fordBellman(s): ford[v] = d[s] = 0 for i = 0 to for if d[v] > d[u] + // — вес ребра uv d[v] = d[u] + for if d[v] > d[u] + return false return true
В этом алгоритме используется релаксация, в результате которой уменьшается до тех пор, пока не станет равным .
— оценка веса кратчайшего пути из вершины в каждую вершину .
— фактический вес кратчайшего пути из в вершину .
Лемма: |
Пусть — взвешенный ориентированный граф, — стартовая вершина. Тогда после завершения итераций цикла для всех вершин, достижимых из , выполняется равенство . |
Доказательство: |
Рассмотрим произвольную вершину , достижимую из . Пусть , где , — кратчайший ациклический путь из в . Путь содержит не более ребер. Поэтому .Докажем следующее утверждение:
Воспользуемся индукцией по :База индукции
Индукционный переход
|
Теорема: |
Пусть — взвешенный ориентированный граф, — стартовая вершина. Если граф не содержит отрицательных циклов, достижимых из вершины , то алгоритм возвращает и для всех . Если граф содержит отрицательные циклы, достижимые из вершины , то алгоритм возвращает . |
Доказательство: |
Пусть граф не содержит отрицательных циклов, достижимых из вершины .Тогда если вершина достижима из , то по лемме . Если вершина не достижима из , то из несуществования пути.Теперь докажем, что алгоритм вернет значение .После выполнения алгоритма верно, что для всех , значит ни одна из проверок не вернет значения .Пусть граф содержит отрицательный цикл , где , достижимый из вершины . Тогда .Предположим, что алгоритм возвращает , тогда для выполняется .Просуммируем эти неравенства по всему циклу: .Из того, что Получили, что следует, что . , что противоречит отрицательности цикла . |
Сложность
Инициализация занимает
времени, каждый из проходов требует времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает времени. Значит алгоритм Беллмана-Форда работает за времени.Нахождение отрицательного цикла
Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно хранить вершины, из которых производится релаксация.
Если после
итерации найдется вершина , расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно раз пройти назад по предкам из вершины . Так как наибольшая длина пути в графе из вершин равна , то полученная вершина будет гарантированно лежать на отрицательном цикле.Зная, что вершина
лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина . Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.int[] negativeCycle(s): ford[v] = p[v] = -1 d[s] = 0 for i = 1 to for if d[v] > d[u] + d[v] = d[u] + p[v] = u for if d[v] > d[u] + for i = 0 to v = p[v] u = v while u != p[v] ans.add(v) // добавим вершину к ответу v = p[v] reverse(ans) break return ans
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
- MAXimal :: algo :: Алгоритм Форда-Беллмана