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

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

Алгоритм

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