Алгоритм Форда-Беллмана

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

Алгоритм

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