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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 33: Строка 33:
  
  
:На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла <b> for </b> релаксируются <tex> \mid E[G] \mid </tex> ребер.<br>
+
: Будем вести доказательство по индукции:
:Среди ребер, прорелаксированных во время iитерации, находится ребро <tex> (v_{i-1}, v_{i}) </tex>.
+
: Перед первой фазой кратчайший путь до вершины <tex>s</tex> найден корректно. <tex>d[s] = 0</tex>
 +
: Во время первой фазы ребро <tex>(v_0, v_1)</tex> было просмотрено алгоритмом Форда-Беллмана, следовательно, расстояние до вершины <tex>v_1</tex> было корректно посчитано после первой фазы.
 +
: Повторяя эти утверждения <tex>k</tex> раз, получаем, что после <tex>k</tex>фазы расстояние до вершины <tex>v</tex> посчитано корректно, что и требовалось доказать.
  
:Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.
+
 
 +
:Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.<br>
 
}}
 
}}
  
Строка 64: Строка 67:
 
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
 
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
  
== Литература ==
+
== Источники ==
 
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
 
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
 +
:[http://e-maxx.ru/algo/export_ford_bellman Алгоритм Форда-Беллмана]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах]]
 
[[Категория: Кратчайшие пути в графах]]

Версия 04:21, 28 октября 2011

Алгоритм

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

Псевдокод

Bellman_Ford(G, s)
  for для каждой [math]v \in V[G][/math]
     [math] d[v] \leftarrow \mathcal {1} [/math]
  [math]d[s] \leftarrow 0 [/math]
  for [math] i \leftarrow 1 [/math] to [math] \mid V[G] \mid - 1 [/math]
     for для каждого ребра [math] (u, v) \in E[G] [/math]
           if [math]d[v] \gt  d[u] + \omega(u, v) [/math]
                 then [math]d[v] \leftarrow d[u] + \omega(u, v)[/math]
  for для каждого ребра [math] (u, v) \in E[G] [/math]
     if [math]d[v] \gt  d[u] + \omega(u, v) [/math]
           then return [math] \mathit false[/math]
  return [math] \mathit true [/math]

Корректность алгоритма Форда-Беллмана

В этом алгоритме используется релаксация, в результате которой [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] \mid V[G] \mid - 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] \mid V[G] \mid - 1 [/math] ребер. Поэтому [math]k \le \mid V[G] \mid - 1[/math].


Будем вести доказательство по индукции:
Перед первой фазой кратчайший путь до вершины [math]s[/math] найден корректно. [math]d[s] = 0[/math]
Во время первой фазы ребро [math](v_0, v_1)[/math] было просмотрено алгоритмом Форда-Беллмана, следовательно, расстояние до вершины [math]v_1[/math] было корректно посчитано после первой фазы.
Повторяя эти утверждения [math]k[/math] раз, получаем, что после [math]k[/math]-й фазы расстояние до вершины [math]v[/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[G] \ 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[G], \ 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})} \ge 0 [/math], что противоречит отрицательности цикла [math] c [/math].
[math]\triangleleft[/math]

Сложность

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

Источники

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
Алгоритм Форда-Беллмана