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

Кількість шляхів довжини [math]k[/math] ребер можна знайти за допомогою методу динамічного програмування. Нехай [math]d[k][u][/math] — кількість шляхів довжини [math]k[/math] ребер, що закінчуються у вершині [math]u[/math]. Тоді [math] d [k] [u] = \ sum \ limits_ d [k-1] [v] [/ math] .

Аналогічно порахуємо шляхи найкоротшої довжини. Нехай [math] s [/ math] - стартова вершина. Тоді [math] d[k][u] = \min\limits_(d[k-1][v] \: + \: \omega(u, v))[/math] , при цьому [math]d [0][s] = 0[/math] , а [math]d[0][u] = +\infty [/math]

Використовуючи наведені формули, алгоритм можна реалізувати методом динамічного програмування.

Також релаксацію можна звести до одновимірної нагоди, якщо не зберігати довжину шляху в ребрах. Одномірний масив будемо позначати [math]d'[/math] , тоді [math]d'[u] = \min(d'[u], \; d'[v] + \omega(vu))[/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_ d[i][u][/math] для всіх [math]u[/math]. Тоді після [math]k[/math] ітерацій [math] \rho(s, v) = \min\limits_(\rho(s, u) + \omega(uv)) \leqslant \min\limits_(d'[u] + \omega(uv)) = d'[v][/math] .

Переходимо до другої нерівності. Тепер можливі два випадки:

[math]\min\limits_d[i][u] = d[k+1][u][/math]
[math]\min\limits_d[i][u] = d[j][u] =\min\limits_\; d[i][u][/math]

Розглянемо один випадок: [math]\min\limits_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] 2 випадокрозписується аналогічно. Таким чином перехід виконаний і [math]\rho(s, u) \leqslant d'[u] \leqslant \min\limits_d[i][u][/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]v[/math], досяжну з [math]s[/math]. Нехай [math] p = \ langle v_0. v_ \rangle [/math] , де [math]v_0 = s[/math] , [math]v_ = v[/math] — найкоротший ациклічний шлях з [math] s [/math] до [math] v [/ math]. Шлях [math] p [/math] містить трохи більше [math] V - 1 [/math] ребер. Тому [math] k \ leqslant V - 1 [/ math].

Доведемо таке твердження:

Після [math]n : (n \leqslant 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_)[/math] належить найкоротшому шляху від [math]s[/math] до [math]v[/math] , то [math]\delta(s, v_) = \delta (s, v_n) + \ omega (v_n, v_) [/ math]. Під час [math]l + 1[/math] ітерації релаксується ребро [math](v_n,v_)[/math] , отже після завершення ітерації буде виконано [math]d[v_] \leqslant d[v_n] + \omega (v_n, v_) = \delta(s, v_n) + \omega(v_n, v_) = \delta(s, v_)[/math]. Зрозуміло, що [math]d[v_] \geqslant \delta(s, v_) [/math] ,тому вірно, що після [math]l + 1[/math] ітерації [math]d[v_] = \delta(s, v_)[/math] . Індукційний перехід доведено. Отже, виконані рівності [math]d[v] = d[v_] = \delta(s, v_) = \delta(s, v)[/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 [/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 = > [/math] , де [math] v_0 = v_ [/math] , досяжний з вершини [math] s [/math] . Тоді [math]\sum\limits_^, v_)> \lt 0 [/math] .

Припустимо, що алгоритм повертає [math] true [/math] тоді для [math] i = 1. k [/math] виконується [math] d[v_] \leqslant d[v_] + \omega (v_ , v_) [/math] .

Підсумуємо ці нерівності у всьому циклі: [math]\sum\limits_^ ]> \leqslant \sum\limits_^ ]> + \sum\limits_^, v_)> [/math] .

З того що [math] v_0 = v_ [/math] випливає, що [math] \sum\limits^_ ]> = \sum \limits_^ ]> [/ Math] .

Отримали, що [math] \sum \limits_^, v_)> \geqslant 0 [/math] , що суперечить негативності циклу [math] c [/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] . Це обов'язково станеться, оскільки у циклі негативної ваги релаксації відбуваються по колу.