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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 21: Строка 21:
 
{{Лемма
 
{{Лемма
 
|statement=Пусть <tex>G = (V, E) </tex> -взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из s выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
 
|statement=Пусть <tex>G = (V, E) </tex> -взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из s выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=Рассмотрим произвольную вершину <tex> v </tex> достижимую из <tex> s </tex>, <tex> p = {v_0,..., v_{k}} </tex>, где <tex> v_0 = s </tex>, <tex> v_{k} = v </tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла релаксируются <tex> \mid E[G] \mid </tex> ребер. Среди ребер, прорелаксированных во время i-й итерации находится ребро <tex> (v_{i-1}, v_{i}) </tex>. Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>
+
|proof=Рассмотрим произвольную вершину <tex> v </tex> достижимую из <tex> s </tex>, <tex> p = {v_0,..., v_{k}} </tex>, где <tex> v_0 = s </tex>, <tex> v_{k} = v </tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла релаксируются <tex> \mid E[G] \mid </tex> ребер. Среди ребер, прорелаксированных во время i-й итерации находится ребро <tex> (v_{i-1}, v_{i}) </tex>. Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=Пусть <tex>G = (V, E) </tex> -взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V[G] \  d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>
 +
|proof=Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути. Теперь докажем что алгоритм вернет значение <tex> true </tex>. После выполнения алгоритма верно, что для всех <tex> (u, v) \in E[G], \  d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.
 +
Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. Тогда <tex>\sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>. Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>. Просуммируем эти неравенства по всему циклу: <tex>\sum_{i=1}^{k} {d[v_{i}]} \leqslant \sum_{i=1}^{k} {d[v_{i-1}]} + \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>. Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum^{k}_{i=1} {d[v_{i}]} = \sum_{i=1}^{k} {d[v_{i - 1}]} </tex>. Получили, что <tex> \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} >= 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
 
}}
 
}}
 
==Сложность==
 
==Сложность==
 
Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
 
Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.

Версия 07:53, 1 декабря 2010

Эта статья находится в разработке!

Алгоритм

Для заданного взвешенного графа [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]
    do [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]
     do for для каждого ребра [math] (u, v) \in E[G] [/math]
           do 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]
     do if [math]d[v] \gt  d[u] + \omega(u, v) [/math]
           then return [math] \mathit false[/math]
  return [math] \mathit true [/math]

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

Лемма:
Пусть [math]G = (V, E) [/math] -взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math] \mid V[G] \mid - 1 [/math] итераций цикла для всех вершин, достижимых из s выполняется равенство [math] d[v] = \delta (s, v) [/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим произвольную вершину [math] v [/math] достижимую из [math] s [/math], [math] p = {v_0,..., v_{k}} [/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] \mid V[G] \mid - 1 [/math] итераций цикла релаксируются [math] \mid E[G] \mid [/math] ребер. Среди ребер, прорелаксированных во время i-й итерации находится ребро [math] (v_{i-1}, v_{i}) [/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_{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_{i=1}^{k} {d[v_{i}]} \leqslant \sum_{i=1}^{k} {d[v_{i-1}]} + \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} [/math]. Из того, что [math] v_0 = v_{k} [/math] следует, что [math] \sum^{k}_{i=1} {d[v_{i}]} = \sum_{i=1}^{k} {d[v_{i - 1}]} [/math]. Получили, что [math] \sum_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \gt = 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] времени.