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

Алгоритъмът на Белман—Форд намира най-късите пътища от един връх до всички останали върхове в насочен тегловен граф. По-бавен е от алгоритъма на Дейкстра, но е много по-гъвкав, когато се обхождат графи с отрицателни тегла на ребрата. Алгоритъмът е именуван на двама от създателите си – Ричард Белман и Лестър Форд младши. Публикуван е през 1958 г. и 1956 г. съответно. Едуард Ф. Мур публикува същия алгоритъм през 1957 г. и поради тази причина алгоритъмът се среща понякога като алгоритъм на Белман—Форд—Мур.

Ако един граф съдържа цикъл с отрицателен сбор от теглата на ребрата и ако този цикъл е достижим от началния връх, то няма най-къс път: всеки път може да се направи още по-къс при още едно обхождане на отрицателния цикъл. В такъв случай алгоритъмът на Белман—Форд може да намери отрицателните цикли и да съобщи за съществуването им.

Алгоритъм

Също както алгоритъма на Дейкстра, алгоритъмът на Белман—Форд се основава на идеята за релаксация: приблизителното разстояние постепенно се заменя с по-точни стойности, докато се намери оптимално решение. И в двата алгоритъма приблизителното разстояние до всеки връх е винаги надценено спрямо действителното разстояние. За разлика от алгоритъма на Дейкстра, който на всяка стъпка избира необработения връх с най-малко тегло и извършва релаксация на ребрата, излизащи от този връх, алгоритъмът на Белман—Форд на всяка стъпка релаксира всички ребра и прави това $|V|-1$ пъти, където $|V|$ е броят на върховете в графа. След всяка итерация броят на върховете с точно пресметнати разстояния расте, от което следва че в края всички върхове ще имат точни разстояния. Затова алгоритъмът на Белман—Форд може да се прилага към по-широко множество от входни данни в сравнение с алгоритъма на Дейкстра.

Времевата сложност на алгоритъма на Белман—Форд е $O(|V|\cdot |E|)$ пъти, където $|V|$ е броят на върховете, а $|E|$ е броят на ребрата на графа.

function BellmanFord(list vertices, list edges, vertex source)
   ::distance[],predecessor[]

   // Това изпълнение взема граф, представен като
   // списъци от върхове и ребра, и запълва два масива
   // (разстояние и предшественик) с информация за най-късия път

   // Стъпка 1: Инициализиране на граф
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := inf
       predecessor[v] := null

   // Стъпка 2: Релаксиране на ребрата с повторение
  
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Стъпка 3: Проверка за негативни-теглови цикли
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"
   return distance[], predecessor[]

Алгоритъмът инициализира разстоянието до началния връх със стойност 0, а за останалите върхове – със стойност безкрайност. След това за всички ребра проверява дали разстоянието до крайния им връх може да се намали и ако да – обновява това разстояние до новата по-малка стойност. След итерация № $i$ е сигурно, че алгоритъмът е намерил всички най-къси пътища с не повече от $i$ ребра. Тъй като най-дългият път без цикъл има максимум $|V|-1$ ребра, то ребрата трябва да бъдат обходени $|V|-1$ пъти, за да е сигурно, че са намерени най-късите пътища до всички върхове. Последното обхождане (с номер $|V|$ ) служи за проверка: ако някое разстояние се промени, тогава е намерен по-къс път с дължина $|V|$ ребра; това може да се случи само ако съществува отрицателен цикъл.

Доказателство за коректност

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

Лема. След i повторения на цикъла for :

Ако разстоянието(u) не е безкрайност, то е равно на дължината на някой от пътищата между връх s и връх u;
Ако има път от връх s до връх u с не повече от i ребра, то тогава разстоянието(u) е не по-голямо от дължината на най-късия път от връх s до връх u с не повече от i ребра.

Доказателство. Основният случай на индукция се разглежда за i=0 и момента преди for цикъла да е изпълнен за първи път. Тогава за началния връх source.distance = 0, което е вярно. За другите върхове u, u.distance = infinity, което също е вярно, защото няма път от началния връх до връх u с 0 ребра.

За индуктивния случай първо се доказва първата част. Разглежда се момента, когато разстоянието до даден връх се определи чрез v.distance := u.distance + uv.weight. u.distanceе дължината на път от началния връх до връх u. Тогава u.distance + uv.weight е дължината на пътя от s до v, който минава през u.

За втората част се разглежда най-късия път от началния връх до u с не повече от i ребра. Нека последният връх преди u от този път да бъде v. Тогава частта от s до v е най-късия път с не повече от i-1 ребра. v.distance след i−1 итерации е не по-голямо от дължината на този път. Следователно uv.weight + v.distance е не по-голямо от пътя от s до u. На i^тата итерация, u.distance се сравнява с uv.weight + v.distanceи ако стойността му е по-голяма, тогава му се присвоява тази на uv.weight + v.distance. Затова след i итерации, u.distance e не по-голямо от дължината на най-краткия път от s до u, който минава през не повече от i ребра.

Ако няма отрицателни цикли, всеки най-кратък път преминава през всеки връх най-много по веднъж. Поради тази причина в стъпка 3 не могат да се правят повече оптимизации. А сега обратното, нека предположим, че подобрения не могат да бъдат направени. Тогава за всеки цикъл с върхове v[0], ..., v[k−1], ако е изпълнено

v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight, то тогава

след края на сумирането на изразите за разстоянията v[i] и v[i−1 (mod k)] в цикъла се получава

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

т.е. няма отрицателни цикли.

Намиране на отрицателни цикли

Когато алгоритъмът се използва за да намери най-късите пътища, наличието на отрицателни цикли е проблем, който пречи на алгоритъма да намери правилено решение. Тъй като той прекратява изпълнението си при намиране на отрицателен цикъл, Белман-Форд алгоритъмът може да бъде използван за приложения в които това е търсената цел – например в техники за анулиране на цикъл при анализи на мрежови поток.

Приложения в маршрутизация

Разпространен вариант на алгоритъма на Белман-Форд се използва в дистанционно векторни протоколи за маршрутизация, например Маршрутизиращият Информационен Протокол (RIP). Алгоритъмът се разпределя, тъй като включва редица възли (рутери) в автономна система, колекция от IP мрежи, обикновено собственост на един доставчик на интернет услуги (ISP). Той се състои от следните стъпки:

Всеки възел изчислява разстоянията между себе си и всички други възли в автономната система и съхранява тази информация във вид на таблица.
Всеки възел изпраща своята таблица до всички съседни възли.
Когато един възел получава таблица от своите съседни възли, изчислява най-кратките маршрути до всички други възли и актуализира своята собствена таблица за да отрази промените.

Основните недостатъци на Белман-Форд алгоритъма в тази настройка, са както следва:

Той не мащабира добре.
Промените в мрежовата топология не са отразени бързо, тъй като актуализациите са разделени възел по възел.
Броене до безкрайност (Count to infinity) или когато стойностите по направленията не достигнат до маршрутизаторите.

Подобрения

Алгоритъмът на Белман-Форд може да бъде подобрен на практика (въпреки че не в най-лошия случай) както виждаме в случай, че ако една итерация от основния цикъл на алгоритъма завърши без да са направени никакви промени, то тогава алгоритъмът може незабавно да бъде прекратен, като последващите итерации няма да направят никакви промени. При това условие с преждевременно прекратяване, основният цикъл в някои случаи може да използва много по-малко итерации от колкото |V| − 1, въпреки че в най-лошия случай на алгоритъма, остава непроменен.

Yen (1970) е описал още две подобрения на Белман-Форд алгоритъма за графи без цикли с отрицателна дължина; отново, докато на практика правят алгоритъма по-бърз, те не променят неговото O(|V|*|E|) в най-лошия случай обвързан с времето. Неговото първо подобрение намалява броя на стъпките за релаксация, които трябва да се извършат в рамките на всяка итерация на алгоритъма. Ако даден връх v има разстояние със стойност, която не се е променила от последната релаксация на ребрата тръгващи от v, то тогава тези ребра нямат нужда от последваща релаксация. По този начин, когато броят на върховете с правилно определени стойности на разстоянията расте, то тогава броят на върховете чиито излизащи ребра трябва да бъдат релаксирани, намалява на всяка итерация, което води до постоянни икономии на време за графи, на които броя върхове е близък до максималния възможен.

Второто подобрение на Yen първо присвоява някакъв произволен линеен ред на всички върхове и след това разделя множеството от всички ребра на две подгрупи. Първата група, E_f, съдържа всички ребра (v_i, v_j) така, че i < j; втората, E_b, съдържа ребра (v_i, v_j) така, че i > j. Всеки връх се посещава в ред v₁, v₂, ..., v_|V|, релаксирайки всяко изходящо ребро от този връх в E_b. Всяка итерация от основния цикъл на алгоритъма, след първата, добавя най-малко две ребра към множеството от ребра, чиито релаксирани разстояния намират най-кратките разстояния на пътищата: един от E_f и един от E_b. Тази модификация намалява броя на итерациите, в най-лошия случай, на основния цикъл на алгоритъма от |V| − 1 до |V|/2.^[1]^[2]

Друго подобрение, от Bannister & Eppstein (2012), замества произволният линеен ред на върховете използван във второто подобрение на Yen, с произволна пермутация. Поради тази промяна, става много малка вероятността, най-лошият случай от подобрението на Yen (в който ребра, на най-краткия път, стриктно се редуват между двете подгрупи E_f and E_b) да се случи. С произволно разместена върхова подредба, очакваният брой итерации, необходими в основния цикъл, е най-много |V|/3.^[2]

Източници

Оригинални източници

Bellman, Richard. On a routing problem // Quarterly of Applied Mathematics 16. 1958. с. 87 – 90.
Ford Jr., Lester R. Network Flow Theory. Santa Monica, California, RAND Corporation, 14 август 1956.
Moore, Edward F. The shortest path through a maze // Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass., Harvard Univ. Press, 1959, 285 – 292 с.
Yen, Jin Y. An algorithm for finding shortest routes from all source nodes to a given destination in general networks // Quarterly of Applied Mathematics 27. 1970. с. 526 – 530.
Randomized speedup of the Bellman–Ford algorithm // Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. 2012, 41 – 47 с. Архив на оригинала от 2014-04-04 в Wayback Machine.

Други източници

Section 2.3.4: The Bellman-Ford-Moore algorithm // Digraphs: Theory, Algorithms and Applications. First. 2000. ISBN 978-1-84800-997-4.
Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp. 588–592. Problem 24 – 1, pp. 614–615. Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp. 651–655.
Chapter 6: Graph Algorithms // Algorithms in a Nutshell. O'Reilly Media, 2008. ISBN 978-0-596-51624-6. с. 160 – 164.
Kleinberg, Jon, Tardos, Éva. Algorithm Design. New York, Pearson Education, Inc., 2006.
Sedgewick, Robert. Section 21.7: Negative Edge Weights // Algorithms in Java. 3rd. 2002. ISBN 0-201-36121-3. Архив на оригинала от 2008-05-31 в Wayback Machine.

Външни препратки

Източници

↑ Cormen et al., 2nd ed., Problem 24 – 1, pp. 614 – 615.
↑ ^а ^б See Sedgewick's web exercises for Algorithms, 4th ed., exercises 5 and 11 (Посетен на 30 януари 2013).

Тази страница частично или изцяло представлява превод на страницата Bellman–Ford algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] Cormen et al., 2nd ed., Problem 24 – 1, pp. 614 – 615.

[Sedweb-2] а ^б See Sedgewick's web exercises for Algorithms, 4th ed., exercises 5 and 11 (Посетен на 30 януари 2013).

[1]

[2]