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

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

Алгоритм

Для заданного взвешенного графа [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] = +\inf [/math]

Лемма:

Если существует кратчайший путь от [math]s[/math] до [math]t[/math], то [math] \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t][/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][u], \; d[k][v] + \omega(u,v))[/math]

Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать [math]d'[/math]):

[math]d'[u] \gets \min(d'[u], \; d'[v] + \omega(u,v))[/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 +\inf \leqslant +\inf [/math] Индукционный переход. Сначала докажем, что [math] \rho(s, u) \leqslant d'[u][/math]. Предположим, что [math]d'[u] + \omega(vu) \geqslant \omega(Path(s \to v) \circ (vu))[/math], то есть вес любого найденного пути больше чем [math]\rho(s, u)[/math], что неверно, следовательно неравенство выполняется. Переходим ко второму неравенству, когда [math]d'[u][/math] изменилось. [math]d'[u] \leqslant \min\limits_{i = 0..k} d[i][u][/math] выполняется, так как [math]d'[u][/math] могло только уменьшится, то это неравенство выполняется. Теперь возможно два случая: [math]\min\limits_{i = 0..k-1} d[i][u] = d[k+1][u][/math] [math]\min\limits_{i = 0..k-1} d[i][u] = \min\limits_{i = j} d[j][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]

В этом алгоритме используется релаксация, в результате которой [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]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[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.

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