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

Броят на пътищата с ръбове с дължина [math] k [/ math] може да бъде намерен с помощта на метода за динамично програмиране.
Нека [math] d [k] [u] [/ math] е броят на пътеките с дължини [math] k [/ math] ръбове, завършващи на върха [math] u [/ math]. Тогава [математика] d [k] [u] = \ сума \ граници_ d [k-1] [v] [/ math] .

По същия начин изчисляваме пътищата с най-късата дължина. Нека [math] s [/ math] е началният връх. Тогава [math] d [k] [u] = \ min \ limit_ (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] 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 \ limit_ d [i] [u] [/ math] за всички [ математика] u [/ math]. След това след [math] k [/ math] итерации [math] \ rho (s, v) = \ min \ limit_ (\ rho (s, u) + \ omega (uv)) \ leqslant \ min \ limit_ (d '[u] + \ omega (uv)) = d' [v] [/ math] .

Преминаваме към второто неравенство. Сега са възможни два случая:

1. [математика] \ мин \ граници_ d [i] [u] = d [k + 1] [u] [/ math]
2. [математика] \ мин \ граници_ d [i] [u] = d [j] [u] = \ мин \ граници_ \; d [i] [u] [/ math]

Да разгледаме случай 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] 2 случай се подписва по същия начин. По този начин преходът е завършен и [math] \ rho (s, u) \ leqslant d '[u] \ leqslant \ min \ limit_ 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] p [/ math] съдържа най-много [math] | V | - 1 [/ math] ръба. Следователно [математика] k \ leqslant | V | - 1 [/ математика] .

Нека докажем следното твърдение:

След [math] n: (n \ leqslant k) [/ math] итерации от първия цикъл на алгоритъма, [math] d [v_n] = \ delta (s, v_n) [/ math]

---