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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Нахождение отрицательного цикла)
(Стилистика)
Строка 2: Строка 2:
  
 
==Алгоритм==
 
==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>
+
Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.
:В, случае, когда в графе <tex> G </tex> содержатся отрицательные циклы, достижимые из <tex> s</tex>, алгоритм сообщает, что кратчайших путей не существует.
+
В, случае, когда в графе <tex>G</tex> содержатся отрицательные циклы, достижимые из <tex>s</tex>, алгоритм сообщает, что кратчайших путей не существует.
  
 
==Введение==
 
==Введение==
:Сначала стоит вспомнить формулу для количества путей длины <tex>k</tex>.
+
Сначала стоит вспомнить формулу для количества путей длины <tex>k</tex>.
::<tex> d[k][u] = \sum\limits_{v : vu \; \in E}  d[k-1][v] </tex>
+
<tex> d[k][u] = \sum\limits_{v : vu \; \in E}  d[k-1][v] </tex>
:Теперь перепишем ее для пути кратчайшей длины. <tex>s</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> 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>
  
 
{{Лемма
 
{{Лемма
|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>,<br> то <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>
|proof=:Пусть кратчайший путь состоит из <tex>k</tex> ребер, тогда корректность формулы следует из динамики, приведенной ниже.<br>
+
|proof=Пусть кратчайший путь состоит из <tex>k</tex> ребер, тогда корректность формулы следует из динамики, приведенной ниже.
 
}}
 
}}
  
 
==Псевдокод==
 
==Псевдокод==
:Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
+
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
  
 
   '''for''' <tex>(k = 0 \; .. \; n-2)</tex>
 
   '''for''' <tex>(k = 0 \; .. \; n-2)</tex>
      '''for''' <tex>(v \in V)</tex>
+
    '''for''' <tex>(v \in V)</tex>
          '''for''' <tex>(u : vu \; \in E)</tex>
+
        '''for''' <tex>(u : vu \; \in E)</tex>
              <tex>d[k+1][u] \gets \min(d[k + 1][u], \; d[k][v] + \omega(uv))</tex>
+
          <tex>d[k+1][u] \gets \min(d[k + 1][u], \; d[k][v] + \omega(uv))</tex>
  
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
+
Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
:<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(vu))</tex>
+
<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(vu))</tex>
  
 
==Корректность==
 
==Корректность==
  
 
{{Лемма
 
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex>k</tex> итераций цикла <tex>for(k)</tex> выполняется неравенство <tex> \rho(s, u) \leqslant d'[u] \leqslant  \min\limits_{i = 0..k} d[i][u]</tex>.
+
|statement=Пусть <tex>G = (V, E)</tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.
|proof=: Воспользуемся индукцией по <tex>k</tex>:
+
Тогда после завершения <tex>k</tex> итераций цикла <tex>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>k = 0</tex> выполнено: <tex>\rho(s, u) \leqslant +\infty \leqslant +\infty </tex>
+
'''База индукции'''  
: '''Индукционный переход.'''
+
:При <tex>k = 0</tex> выполнено: <tex>\rho(s, u) \leqslant +\infty \leqslant +\infty </tex>
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
 
::Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..n-1} d[i][u]</tex> для всех <tex>u</tex>.
 
::Тогда после <tex>k</tex> итераций <tex> \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]</tex>.
 
  
 +
'''Индукционный переход'''
 +
:Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
 +
:Пусть после <tex>k - 1 </tex> итерации выполняется <tex>\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i=0..n-1} d[i][u]</tex> для всех <tex>u</tex>.
 +
:Тогда после <tex>k</tex> итераций <tex> \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]</tex>.
  
::Переходим ко второму неравенству.
 
::Теперь возможно два случая:
 
::#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex>
 
::#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[j][u] =\min\limits_{i = 0..j} \; d[i][u]</tex>
 
  
 +
:Переходим ко второму неравенству.
 +
:Теперь возможно два случая:
 +
:#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex>
 +
:#<tex>\min\limits_{i = 0..k+1} d[i][u] = d[j][u] =\min\limits_{i = 0..j} \; d[i][u]</tex>
  
::Рассмотрим 1 случай:
+
 
:::<tex>\min\limits_{i = 0..k+1} d[i][u] = d[k+1][u]</tex><br>
+
:Рассмотрим 1 случай:
:::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</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>
 
::<tex>\vartriangleleft</tex>
 
::<tex>\vartriangleleft</tex>
::2 случай расписывается аналогично.
+
:2 случай расписывается аналогично.
 
 
  
:Таким образом переход выполнен и <tex>\rho(s, u) \leqslant d'[u] \leqslant  \min\limits_{i = 0..k} d[i][u]</tex> выполняется.
+
Таким образом переход выполнен и <tex>\rho(s, u) \leqslant d'[u] \leqslant  \min\limits_{i = 0..k} d[i][u]</tex> выполняется.
<br>
 
 
}}
 
}}
 
  
 
==Реализация алгоритма и ее корректность==
 
==Реализация алгоритма и ее корректность==
 
 
 
  '''Bellman_Ford(G, s)'''
 
  '''Bellman_Ford(G, s)'''
  '''for''' для каждой <tex>v \in V</tex>
+
    '''for''' для каждой <tex>v \in V</tex>
      <tex> d[v] \leftarrow \mathcal {1} </tex>
+
      <tex> d[v] \leftarrow \mathcal {1} </tex>
  <tex>d[s] \leftarrow 0 </tex>
+
    <tex>d[s] \leftarrow 0 </tex>
  '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V \mid - 1 </tex>
+
    '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> |V| - 1 </tex>
      '''for''' для каждого ребра <tex> (u, v) \in E </tex>
+
      '''for''' для каждого ребра <tex> (u, v) \in E </tex>
            '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
+
          '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
                  '''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
+
            '''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
  '''for''' для каждого ребра <tex> (u, v) \in E </tex>
+
    '''for''' для каждого ребра <tex> (u, v) \in E </tex>
      '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
+
      '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
            '''then''' '''return''' <tex> \mathit false</tex>
+
          '''then''' '''return''' <tex> \mathit false</tex>
  '''return''' <tex> \mathit true </tex>
+
    '''return''' <tex> \mathit true </tex>
  
  
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. <br>
+
В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>.
:<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br>
+
<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br>
:<tex>\delta(s, v)</tex> - фактический вес кратчайшего пути из  <tex>s</tex> в вершину <tex>v</tex>.
+
<tex>\delta(s, v)</tex> - фактический вес кратчайшего пути из  <tex>s</tex> в вершину <tex>v</tex>.
  
  
 
{{Лемма
 
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex> \mid V \mid - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
+
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> |V| - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=:Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.
+
|proof=Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.
 
+
Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> |V| - 1 </tex> ребер. Поэтому <tex>k \le |V| - 1</tex>.
 
 
:Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>.<br>
 
:Путь <tex> p </tex> содержит не более <tex> \mid V \mid - 1 </tex> ребер. Поэтому <tex>k \le \mid V \mid - 1</tex>.
 
  
 +
Докажем следующее утверждение:
 +
:После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
 +
Воспользуемся индукцией по <tex>n</tex>:
  
: Докажем следующее утверждение:
+
'''База индукции'''
:: После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
+
:Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] = d[s] = \delta(s, s) = 0</tex>
: Воспользуемся индукцией по <tex>n</tex>:
+
'''Индукционный переход'''
: '''База индукции.''' Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] = d[s] = \delta(s, s) = 0</tex>
+
:Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
: '''Индукционный переход.''' Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
 
 
::<tex>d[v_{n+1}] \le d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex>.
 
::<tex>d[v_{n+1}] \le d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex>.
: Ясно, что <tex>d[v_{n+1}] \ge \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.  
+
:Ясно, что <tex>d[v_{n+1}] \ge \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.  
: Индукционный переход доказан.
+
:Индукционный переход доказан.
  
 +
Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)</tex>.<br>
 +
}}
  
: Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)</tex>.<br>
+
{{Теорема
}}
+
|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> 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>.
|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V \  d[v] = \delta (s, v)</tex>.<br>Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>
 
|proof=:Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>.<br>
 
:Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>.<br>
 
:Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути.  
 
  
 +
После выполнения алгоритма верно, что для всех <tex> (u, v) \in E, \  d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.
  
:Теперь докажем, что алгоритм вернет значение <tex> true </tex>.<br>
+
Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. Тогда <tex>\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>.
:После выполнения алгоритма верно, что для всех <tex> (u, v) \in E, \  d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </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> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>.<br>
+
Просуммируем эти неравенства по всему циклу: <tex>\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})} </tex>.
:Тогда <tex>\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>.<br>
 
:Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>.<br>
 
:Просуммируем эти неравенства по всему циклу: <tex>\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})} </tex>.<br>
 
:Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.  
 
  
 +
Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.
  
:Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
+
Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
 
}}
 
}}
  
 
==Сложность==
 
==Сложность==
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
+
Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> |V| - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Значит алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
  
 
==Нахождение отрицательного цикла==
 
==Нахождение отрицательного цикла==
:Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно сохранять массив вершин из которых производится релаксация. Тогда, если после <tex> \mid V \mid - 1 </tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>\mid V \mid - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>\mid V \mid</tex> вершин равна <tex>\mid V \mid - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле. Теперь, зная что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно пройти из нее по предкам, пока не придем в ту же вершину <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
+
Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно запоминать вершины, из которых производится релаксация. Тогда, если после <tex>|V| - 1</tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>|V| - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>|V|</tex> вершин равна <tex>|V| - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле. Теперь, зная что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно пройти из нее по предкам, пока не придем в ту же вершину <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
  
 
   '''Neg_Cycle(G, s)'''
 
   '''Neg_Cycle(G, s)'''
Строка 135: Строка 130:
 
       <tex> p[v] \leftarrow -1 </tex>
 
       <tex> p[v] \leftarrow -1 </tex>
 
   <tex>d[s] \leftarrow 0 </tex>
 
   <tex>d[s] \leftarrow 0 </tex>
   '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V \mid - 1 </tex>
+
   '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex>|V| - 1 </tex>
 
       '''for''' для каждого ребра <tex> (u, v) \in E </tex>
 
       '''for''' для каждого ребра <tex> (u, v) \in E </tex>
 
         '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then'''
 
         '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then'''
Строка 142: Строка 137:
 
   '''for''' для каждого ребра <tex> (u, v) \in E </tex>
 
   '''for''' для каждого ребра <tex> (u, v) \in E </tex>
 
       '''if''' <tex>d[v] > d[u] + \omega(u, v)</tex> '''then'''  
 
       '''if''' <tex>d[v] > d[u] + \omega(u, v)</tex> '''then'''  
         '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V \mid - 1 </tex>
+
         '''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex>|V| - 1 </tex>
 
             <tex>v \leftarrow p[v]</tex>
 
             <tex>v \leftarrow p[v]</tex>
 
         <tex>u \leftarrow v</tex>
 
         <tex>u \leftarrow v</tex>

Версия 10:50, 10 января 2013

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

Алгоритм

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

Введение

Сначала стоит вспомнить формулу для количества путей длины [math]k[/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[uv])[/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 [math](k = 0 \; .. \; n-2)[/math]
    for [math](v \in V)[/math]
       for [math](u : vu \; \in E)[/math]
          [math]d[k+1][u] \gets \min(d[k + 1][u], \; d[k][v] + \omega(uv))[/math]

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

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

Лемма:
Пусть [math]G = (V, E)[/math] — взвешенный ориентированный граф, [math] s [/math] — стартовая вершина. Тогда после завершения [math]k[/math] итераций цикла [math]for(k)[/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..n-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]
[math]\vartriangleleft[/math]
2 случай расписывается аналогично.
Таким образом переход выполнен и [math]\rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u][/math] выполняется.
[math]\triangleleft[/math]

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

Bellman_Ford(G, s)
   for для каждой [math]v \in V[/math]
      [math] d[v] \leftarrow \mathcal {1} [/math]
   [math]d[s] \leftarrow 0 [/math]
   for [math] i \leftarrow 1 [/math] to [math] |V| - 1 [/math]
      for для каждого ребра [math] (u, v) \in E [/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 [/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] |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 \le |V| - 1[/math].

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

После [math]n : (n \le 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}] \le 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}] \ge \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})} \ge 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]. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.

  Neg_Cycle(G, s)
  for для каждой [math]v \in V[/math]
     [math] d[v] \leftarrow \mathcal {1} [/math]
     [math] p[v] \leftarrow -1 [/math]
  [math]d[s] \leftarrow 0 [/math]
  for [math] i \leftarrow 1 [/math] to [math]|V| - 1 [/math]
     for для каждого ребра [math] (u, v) \in E [/math]
        if [math]d[v] \gt  d[u] + \omega(u, v) [/math] then
           [math]d[v] \leftarrow d[u] + \omega(u, v)[/math]
           [math]p[v] \leftarrow p[u][/math]
  for для каждого ребра [math] (u, v) \in E [/math]
     if [math]d[v] \gt  d[u] + \omega(u, v)[/math] then 
        for [math] i \leftarrow 1 [/math] to [math]|V| - 1 [/math]
           [math]v \leftarrow p[v][/math]
        [math]u \leftarrow v[/math]
        while [math] u \neq p[v][/math]
           [math]ans.add(v)[/math]
           [math]v \leftarrow p[v][/math]
        [math]reverse(ans)[/math]
        break
  return [math] ans [/math]

Источники

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