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

	Белман-Фордов алгоритам
Намена	Налажење најкраћег пута (за усмерене тежинске графове)
Структура података	Граф
Временска компл.
Меморијска компл.

Белман-Фордов алгоритам је алгоритам који рачуна најкраћи пут из једног ка свим другим чворовима у тежинском диграфу.^[1] Спорији је од Дејкстриног алгоритма, али је прилагодљивији, зато што може да ради и са графовима чије су неке ивице негативних тежина. Алгоритам је именован по своја два развијаоца, Ричарду Белману и Лестеру Форду Млађем, који су га објавили 1958. и 1956.; међутим, Едвард Ф. Мур је такође објавио исти алгоритам 1957, због чега се алгоритам понекад назива Белман-Форд-Муров алгоритам.^[1]

Ивице са негативним тежинама се могу наћи у многим применама графова, што чини овај алгоритам веома корисним.^[2] Међутим, ако граф садржи "негативни циклус", нпр., циклус чије ивице имају негативни збир, онда нема најјефтинијег пута, зато што у том случају сваки пут може постати јефтинији ако се још једном прође кроз негативни циклус. У таквим случајевима, Белман-Фордов алгоритам може открити негативне циклусе и пријавити њихово постојање, али не може произвести тачан најкраћи пут уколико се до негативног циклуса може доћи из почетног чвора.^[1]^[3]

Алгоритам

Као и Дејкстрин алгоритам, Белман-Фордов је основан на принципу итеративне методе по имену релаксација, у коме се апроксимација тачне удаљености постепено смењује тачнијом вредношћу све док се евентуално не достигне оптимално решење. У оба алгоритма, приближна удаљеност до сваког чвора је увек прецењена вредност тачне удаљености, и замењује се минимумом своје старе вредности и дужине новооткривеног пута. Међутим, Дејкстрин алгоритам похлепно бира чвор са најмањом тежином који још увек није посећен, и понавља исти поступак на свим осталим ивицама; у поређењу, Белман-Фордов алгоритам једноставно релаксира све ивице, и то чини |V | − 1 пута, где је |V | број чворова у графу. У сваком новом понављању, број чворова са тачно израчунатом удаљености расте, одакле следи да ће евентуално сви чворови имати тачно израчунате удаљености. Ова метода допушта Белман-Фордовом алгоритму да се користи на ширу класу улаза од Дејкстриног.

Белман-Форд се извршава у времену O(|V|·|E|), где су |V| и |E| бројеви чворова и ивица.

procedure BellmanFord(list vertices, list edges, vertex source)
   // Ova implementacija prima graf, predstavljen kao lista čvorova – vertices,
   // i ivica - edges, i popunjava dva niza (udaljenost – distance,
   // prijethodnik – predecessor) informacijama o najkraćem putu

   // Korak 1: Inicijalizacija grafa
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Korak 2: Ponovljena relaksacija ivica
   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

   // Korak 3: Provjera da li postoje ciklusi sa negativnom težinom
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"

Доказ коректности

Коректност алгоритма се може показати математичком индукцијом.

Лема. Након i понављања for петље:

Ако Distance(u) није бесконачно, онда је једнако дужини путање од s до u;
Ако постоји пут од s до u са највише i ивица, онда Distance(u) није веће од дужине најкраћег пута од s до u са највише i ивица.

Доказ. За базни случај индукције, разматрајмо i = 0 и тренутак пре него што је for петља покренута по први пут. У том случају је, за почетни чвор, source.distance = 0, што је тачно. За остале чворове u важи u.distance = infinity, што је такође тачно, зато што не постоји пут из source до u сачињен од 0 ивица.

У индуктивном кораку, прво доказујемо први корак. Разматрајмо тренутак када се удаљеност чвора мења са v.distance := u.distance + uv.weight. По индуктивној хипотези, u.distance је дужина неког пута од source до u. онда је u.distance + uv.weight дужина пута од source до v која прати пут од source до u а онда иде до v.

Што се тиче другог корака, разматрајмо најкраћи пут од source до u са највише i ивица. Нека је v чвор пре u на овом путу. Онда, део пута од source до v је најкраћи пут од source до v са највише i-1 ивица. По индуктивној хипотези, v.distance после i−1 итерација петље није већа од дужине овог пута. Одатле следи да uv.weight + v.distance није већа од дужине пута од s до u. У i-toj итерацији, u.distance се пореди са uv.weight + v.distance, и једнака јој је уколико је uv.weight + v.distance било мање. Дакле, после i итерација, u.distance није веће од дужине најкраћег пута од source до u са највише i ивица.

Уколико нема циклуса са негативном тежином, онда сваки најкраћи пут посети сваки чвор највише једном, тако да се у трећем кораку не може направити неко побољшање. Насупрот томе, претпоставимо да се не може направити побољшање. онда за сваки циклус са чворовима v[0], ..., v[k−1] важи,

v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight

Сумирањем око циклуса, v[i].distance и v[i−1 (mod k)] distance се потиру, остављајући 0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

То јест, сваки циклус има ненегативну вредност.

Налажење негативних циклуса

Када се алгоритам користи за претрагу најкраћег пута, постојање негативних циклуса је проблем који спречава алгоритам да пронађе тачан одговор. Међутим, с обзиром да стаје када наиђе на негативни циклус, Белман-Фордов алгоритам се може користити у апликацијама у којој је то циљ - на пример у техникама поништавања циклуса у анализи транспортационих мрежа.^[1]

Примена у рутирању

Дистрибуирана варијанта Белман-Фордовог алгоритма се користи у протоколима рутирања на основу вектора удаљености, на пример, у RIP-у. Алгоритам је дистрибуиран зато што укључује неки број чворова (рутера) унутар аутономног система, скупа IP мрежа које су углавном у власништву неког ISP-а. Састоји се из следећих корака:

Сваки чвор рачуна растојање између себе и свих других чворова унутар AS-а и складишти ову информацију унутар табеле.
Сваки чвор шаље своју табелу суседним чворовима.
Када чвор прими табелу од својис суседа, он израчунава најкраћу путању до свих других чворова и мења своју табелу уколико је дошло до неких промена.

Главне мане Белман-Фордовог алгоритма у овом окружењу су:

Скалирање се не врши добро.
Промене у топологији мреже се не одражавају брзо, пошто се исправке шире са чвора на чвор.
Проблем бројења до бесконачности (уколико услед неке грешке дође до тога да је неки чвор недостижан из неког скупа других чворова, ти чворови могу да повећавају своје процене растојања до недостижног чвора).

Унапређења

Белман-Фордов алгоритам се може унапредити у пракси (али не и у најгорем случају) уз посматрање да, уколико се итерација главне петље алгоритма терминира без прављења неких промена, алгоритам се може истог тренутка терминира, зато што наредне итерације неће правити измене. Уз овај услов, главна петља у неким случајевима има много мање од |V| − 1 итерација, иако најгори случај алгоритма остаје непромењен.

Јен (1970) описује још два унапређења Белман-Фордовог алгоритма за граф без циклуса негативне тежине; опет, иако чине алгоритам бржи у пракси, не мењају његов најгори случај од O(|V|*|E|). Његово прво унапређење смањује број релаксационих корака који су потребни за сваку итерацију алгоритма. Ако чвор v има удаљеност која се није променила од последњег пута када су се ивице које иду из v релаксирале, онда нема потребе релаксирати ивице из v по други пут. На овај начин, како се број чворова са тачним удаљеностима повећава, број ивица које требају да се релаксирају у свакој итерацији смањује, што води до константног уштеђења времена за густе графове.

Јеново друго унапређење прво додељује арбитрарни линеарни ред свим чворовима и онда партиционише скуп свих чворова на два подскупова. Први подскуп, E_f, садржи све ивице (v_i, v_j) такве да је i < j; други подскуп, E_b, садржи ивице (v_i, v_j) такве да је i > j. Сваки чвор је посећен редом v₁, v₂, ..., v_|V|, релаксирајући сваку ивицу која иде од тог чвора из E_f. Сваки чвор се онда посећује редом v_|V|, v_|V|−1, ..., v₁, релаксирајући сваку ивицу која иде из чвора E_b. Свака итерација у главној петљи алгоритма, после прве, додаје барем две ивице у скуп ивица чије се релаксиране удаљености поклапају са тачним најкраћим путем: једна из E_f и једна из E_b. Ова модификација смањује број итерација главне петље у најгорем случају са |V| − 1 на |V|/2.^[4]^[5]

Још једно унапређење од стране Банистера и Епштајна (2012), замењује арбитрарни линеарни ред чворова коришћених у Јеновом другом унапређењу са насумичном пермутацијом. Ова промена чини да се најгори случај за Јеново унапређење (у коме чворови најкраћег пута стриктно алтернирају између два подскупа E_f и E_b) веома тешко догоди. Са насумичном пермутацијом редоследа чворова, очекивана вредност за број итерација потребних у главној петњи је највише |V|/3.^[5]

Референце

^ ^а ^б ^в ^г Bang-Jensen & Gutin 2000
^ Sedgewick 2002
^ Kleinberg & Tardos 2006
^ Cormen et al., 2nd ed., Problem 24-1, pp. 614–615.
^ ^а ^б Погледајте Сеџвикова вежбања под Algorithms, 4th ed., вежбања 5 и 11 (преузето 2013-01-30).

Литература

Оригинални извори

Bellman, Richard (1958). „On a routing problem”. Quarterly of Applied Mathematics. 16: 87—90. MR 0102435.
Ford Jr., Lester R. (1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation.
Moore, Edward F. (1959). „The shortest path through a maze”. Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass.: Harvard University Press. стр. 285—292. MR 0114710.
Yen, Jin Y. (1970). „An algorithm for finding shortest routes from all source nodes to a given destination in general networks”. Quarterly of Applied Mathematics. 27: 526—530. MR 0253822.
Bannister, M. J.; Eppstein, D. (2012). „Randomized speedup of the Bellman–Ford algorithm” (PDF). Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. стр. 41—47. arXiv:1111.5414 . Архивирано из оригинала (PDF) 4. 4. 2014. г. Приступљено 29. 5. 2013.

Секундарни извори

Bang-Jensen, Jørgen; Gutin, Gregory (2000). „Section 2.3.4: The Bellman-Ford-Moore algorithm”. Digraphs: Theory, Algorithms and Applications (First изд.). ISBN 978-1-84800-997-4.
Introduction to Algorithms, Second Edition. . MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3. .. 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.
Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). „Chapter 6: Graph Algorithms”. Algorithms in a Nutshell. O'Reilly Media. стр. 160—164. ISBN 978-0-596-51624-6.
Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. New York: Pearson Education, Inc.
Sedgewick (computer scientist), Robert (2002). „Section 21.7: Negative Edge Weights”. Algorithms in Java (3rd изд.). ISBN 978-0-201-36121-6. Архивирано из оригинала 31. 05. 2008. г. Приступљено 29. 05. 2013.

Спољашње везе

Open Source Java пакет за рад са графовима и Белман-Фордовим алгоритмом

[Bang-1] а ^б ^в ^г Bang-Jensen & Gutin 2000

[Sedgewick-2] Sedgewick 2002

[Kleinberg-3] Kleinberg & Tardos 2006

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

[Sedweb-5] а ^б Погледајте Сеџвикова вежбања под Algorithms, 4th ed., вежбања 5 и 11 (преузето 2013-01-30).

[1]

[2]

[3]

[4]

[5]