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

Броят на пътищата с ръбове с дължина [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]

Нека използваме индукция по [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] .

След изпълнението на алгоритъма е вярно, че за всички [математика] (u, v) \ в 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] . Тогава [математика] \ сума \ граници_ ^, v_)> \ lt 0 [/ math] .

Да предположим, че алгоритъмът връща [math] true [/ math], след това за [math] i = 1. k [/ math] [math] d [v_] \ leqslant d [v_] + \ omega (v_, v_) [/ математика] .

Нека да обобщим тези неравенства по целия цикъл: [math] \ sum \ limit_ ^]> \ leqslant \ sum \ limit_ ^]> + \ sum \ limit_ ^, v_)> [/ математика] .

Тъй като [математика] v_0 = v_ [/ математика] следва, че [математика] \ сума \ граници ^ _]> = \ сума \ граници_ ^]> [/ математика] .

Разбрах, че [математика] \ сума \ граници_ ^, 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] време.

Горното изпълнение ви позволява да определите наличието на отрицателно тегло в графиката на цикъла. За да намерите самия цикъл, е достатъчно да съхраните върховете, от които се извършва релаксацията.

Ако след [математика] | 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]. Това със сигурност ще се случи, тъй като в цикъл с отрицателно тегло се появяват релаксации в кръг.