Алгоритм Форда-Беллмана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (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>s</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[uv])</tex>,  при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\infty </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>
 
|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''' n - 2
+
   '''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][u] = min(d[k + 1][u], d[k][v] + <tex>\omega(u, v)</tex>)    <font color="green">// <tex>\omega(u, v)</tex> - вес ребра uv</font>
+
           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'</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(k)}</tex> выполняется неравенство <tex> \rho(s, u) \leqslant d'[u] \leqslant  \min\limits_{i = 0..k} d[i][u]</tex>.
+
Тогда после завершения <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>
::<tex>\vartriangleleft</tex>
 
 
:2 случай расписывается аналогично.
 
:2 случай расписывается аналогично.
  
Строка 57: Строка 55:
  
 
==Реализация алгоритма и ее корректность==
 
==Реализация алгоритма и ее корректность==
  '''bool''' bellman_ford(s)''':'''
+
  '''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[]''' neg_cycle(s)''':'''
+
   '''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 = 0 '''to''' <tex>|V| - 1</tex>
+
       '''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

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


Введение

Количество путей длины [math]k[/math] рёбер можно найти с помощью метода динамического программирования.
Пусть [math]d[k][u][/math] — количество путей длины [math]k[/math] рёбер, заканчивающихся в вершине [math]u[/math]. Тогда [math] d[k][u] = \sum\limits_{v : vu \; \in E} d[k-1][v] [/math].

Аналогично посчитаем пути кратчайшей длины. Пусть [math]s[/math] — стартовая вершина. Тогда [math] d[k][u] = \min\limits_{v : vu \; \in E}(d[k-1][v] \: + \: \omega(u, v))[/math], при этом [math]d[0][s] = 0[/math], а [math]d[0][u] = +\infty [/math]

Лемма:
Если существует кратчайший путь от [math]s[/math] до [math]t[/math], то [math] \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t][/math]
Доказательство:
[math]\triangleright[/math]
Пусть кратчайший путь состоит из [math]k[/math] ребер, тогда корректность формулы следует из динамики, приведенной ниже.
[math]\triangleleft[/math]

Псевдокод

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

 for k = 0 to [math]|V| - 2[/math]                                           // вершины нумеруются с единицы
    for [math]v \in V[/math]
       for [math] (u, v) \in E [/math]
          d[k + 1][v] = min(d[k + 1][v], d[k][u] + [math]\omega(u, v)[/math])     // [math]\omega(u, v)[/math] — вес ребра uv

Также релаксацию можно свести к одномерному случаю, если не хранить длину пути в рёбрах. Одномерный массив будем обозначать [math]d'[/math], тогда [math]d'[u] = \min(d'[u], \; d'[v] + \omega(vu))[/math]

Корректность

Лемма:
Пусть [math]G = (V, E)[/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math]k[/math] итераций цикла [math]\mathrm{for}[/math] выполняется неравенство [math] \rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u][/math].
Доказательство:
[math]\triangleright[/math]

Воспользуемся индукцией по [math]k[/math]:

База индукции

При [math]k = 0[/math] выполнено: [math]\rho(s, u) \leqslant +\infty \leqslant +\infty [/math]

Индукционный переход

Сначала докажем, что [math] \rho(s, u) \leqslant d'[u][/math].
Пусть после [math]k - 1 [/math] итерации выполняется [math]\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..k-1} d[i][u][/math] для всех [math]u[/math].
Тогда после [math]k[/math] итераций [math] \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][/math].


Переходим ко второму неравенству.
Теперь возможно два случая:
  1. [math]\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u][/math]
  2. [math]\min\limits_{i = 0..k+1} d[i][u] = d[j][u] =\min\limits_{i = 0..j} \; d[i][u][/math]


Рассмотрим 1 случай:
[math]\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u][/math]
[math]d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u][/math]
2 случай расписывается аналогично.
Таким образом переход выполнен и [math]\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u][/math] выполняется.
[math]\triangleleft[/math]

Реализация алгоритма и ее корректность

bool fordBellman(s):
    for [math]v \in V[/math]
        d[v] = [math]\mathcal {1}[/math]
    d[s] = 0
    for i = 0 to [math] |V| - 1 [/math]
        for [math] (u, v) \in E [/math]
            if d[v] > d[u] + [math]\omega(u, v)[/math]     // [math]\omega(u, v)[/math] — вес ребра uv
                d[v] = d[u] + [math]\omega(u, v)[/math]
    for [math] (u, v) \in E [/math]
        if d[v] > d[u] + [math]\omega(u, v)[/math]
            return false
    return true


В этом алгоритме используется релаксация, в результате которой [math]d[v][/math] уменьшается до тех пор, пока не станет равным [math]\delta(s, v)[/math]. [math]d[v][/math] — оценка веса кратчайшего пути из вершины [math]s[/math] в каждую вершину [math]v \in V[/math].
[math]\delta(s, v)[/math] — фактический вес кратчайшего пути из [math]s[/math] в вершину [math]v[/math].


Лемма:
Пусть [math]G = (V, E) [/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math] |V| - 1 [/math] итераций цикла для всех вершин, достижимых из [math]s[/math], выполняется равенство [math] d[v] = \delta (s, v) [/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольную вершину [math]v[/math], достижимую из [math]s[/math]. Пусть [math]p = \langle v_0,..., v_{k} \rangle [/math], где [math]v_0 = s[/math], [math]v_{k} = v[/math] — кратчайший ациклический путь из [math] s [/math] в [math] v [/math]. Путь [math] p [/math] содержит не более [math] |V| - 1 [/math] ребер. Поэтому [math]k \leqslant |V| - 1[/math].

Докажем следующее утверждение:

После [math]n : (n \leqslant k)[/math] итераций первого цикла алгоритма, [math]d[v_n] = \delta(s, v_n) [/math]

Воспользуемся индукцией по [math]n[/math]:

База индукции

Перед первой итерацией утверждение очевидно выполнено: [math]d[v_0] = d[s] = \delta(s, s) = 0[/math]

Индукционный переход

Пусть после [math]n : (n \lt k)[/math] итераций, верно что [math]d[v_n] = \delta(s, v_n)[/math]. Так как [math](v_n, v_{n + 1})[/math] принадлежит кратчайшему пути от [math]s[/math] до [math]v[/math], то [math]\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})[/math]. Во время [math]l + 1[/math] итерации релаксируется ребро [math](v_n,v_{n+1})[/math], следовательно по завершению итерации будет выполнено
[math]d[v_{n+1}] \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})[/math].
Ясно, что [math]d[v_{n+1}] \geqslant \delta(s, v_{n+1}) [/math], поэтому верно что после [math]l + 1[/math] итерации [math]d[v_{n+1}] = \delta(s, v_{n + 1})[/math].
Индукционный переход доказан.
Итак, выполнены равенства [math]d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)[/math].
[math]\triangleleft[/math]
Теорема:
Пусть [math]G = (V, E) [/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Если граф [math] G [/math] не содержит отрицательных циклов, достижимых из вершины [math] s [/math], то алгоритм возвращает [math] true [/math] и для всех [math] v \in V \ d[v] = \delta (s, v)[/math]. Если граф [math] G [/math] содержит отрицательные циклы, достижимые из вершины [math] s [/math], то алгоритм возвращает [math] false [/math].
Доказательство:
[math]\triangleright[/math]

Пусть граф [math] G [/math] не содержит отрицательных циклов, достижимых из вершины [math] s [/math].

Тогда если вершина [math] v [/math] достижима из [math] s [/math], то по лемме [math] d[v] = \delta (s, v)[/math]. Если вершина [math] v [/math] не достижима из [math] s [/math], то [math] d[v] = \delta (s, v) = \mathcal {1}[/math] из несуществования пути.

Теперь докажем, что алгоритм вернет значение [math] true [/math].

После выполнения алгоритма верно, что для всех [math] (u, v) \in E, \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)[/math], значит ни одна из проверок не вернет значения [math] false [/math].

Пусть граф [math] G [/math] содержит отрицательный цикл [math] c = {v_0,...,v_{k}} [/math], где [math] v_0 = v_{k} [/math], достижимый из вершины [math] s [/math]. Тогда [math]\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \lt 0 [/math].

Предположим, что алгоритм возвращает [math] true [/math], тогда для [math] i = 1,...,k [/math] выполняется [math] d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) [/math].

Просуммируем эти неравенства по всему циклу: [math]\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})} [/math].

Из того, что [math] v_0 = v_{k} [/math] следует, что [math] \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} [/math].

Получили, что [math] \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \geqslant 0 [/math], что противоречит отрицательности цикла [math] c [/math].
[math]\triangleleft[/math]

Сложность

Инициализация занимает [math] \Theta (V) [/math] времени, каждый из [math] |V| - 1 [/math] проходов требует [math] \Theta (E) [/math] времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает [math]O(E)[/math] времени. Значит алгоритм Беллмана-Форда работает за [math]O(V E)[/math] времени.

Нахождение отрицательного цикла

Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно хранить вершины, из которых производится релаксация.

Если после [math]|V| - 1[/math] итерации найдется вершина [math] v [/math], расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно [math]|V| - 1[/math] раз пройти назад по предкам из вершины [math] v [/math]. Так как наибольшая длина пути в графе из [math]|V|[/math] вершин равна [math]|V| - 1[/math], то полученная вершина [math] u [/math] будет гарантированно лежать на отрицательном цикле.

Зная, что вершина [math] u [/math] лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина [math] u [/math]. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.

 int[] negativeCycle(s):
     for [math]v \in V[/math]
         d[v] = [math]\mathcal {1}[/math]
         p[v] = -1
     d[s] = 0
     for i = 1 to [math]|V| - 1[/math]
         for [math] (u, v) \in E [/math]
             if d[v] > d[u] + [math]\omega(u, v)[/math]
                 d[v] = d[u] + [math]\omega(u, v)[/math]
                 p[v] = u
     for [math] (u, v) \in E [/math]
         if d[v] > d[u] + [math]\omega(u, v)[/math]
             for i = 0 to [math]|V| - 1[/math]
                 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 :: Алгоритм Форда-Беллмана