Belman-Fordov algoritam

Belman-Fordov algoritam

Namena Nalaženje najkraćeg puta (za usmerene težinske grafove) Struktura podataka Graf Vremenska kompl. $O(|V||E|)$ Memorijska kompl. $O(|V|)$

Belman-Fordov algoritam je algoritam koji računa najkraći put iz jednog ka svim drugim čvorovima u težinskom digrafu. Sporiji je od Dejkstrinog algoritma, ali je prilagodljiviji, zato što može da radi i sa grafovima čije su neke ivice negativnih težina. Algoritam je imenovan po svoja dva razvijaoca, Ričardu Belmanu i Lesteru Fordu Mlađem, koji su ga objavili 1958. i 1956.; međutim, Edvard F. Mur je takođe objavio isti algoritam 1957, zbog čega se algoritam ponekad naziva Belman-Ford-Murov algoritam.

Ivice sa negativnim težinama se mogu naći u mnogim primenama grafova, što čini ovaj algoritam veoma korisnim. Međutim, ako graf sadrži "negativni ciklus", npr., ciklus čije ivice imaju negativni zbir, onda nema najjeftinijeg puta, zato što u tom slučaju svaki put može postati jeftiniji ako se još jednom prođe kroz negativni ciklus. U takvim slučajevima, Belman-Fordov algoritam može otkriti negativne cikluse i prijaviti njihovo postojanje, ali ne može proizvesti tačan najkraći put ukoliko se do negativnog ciklusa može doći iz početnog čvora.

Algoritam

U ovom primeru, pod pretpostavkom da je A početni čvor i da se ivice obilaze u najgorem mogućem poredku, zdesna ulevo, potrebno je punih |V|−1 ili 4 iteracija kako bi procene daljine konvergirale. Nasuprot tome, ako su ivice obrađene u najboljem mogućem redosledu, sleva udesno, algoritam konvergira u jednu iteraciju.

Kao i Dejkstrin algoritam, Belman-Fordov je osnovan na principu iterativne metode po imenu relaksacija, u kome se aproksimacija tačne udaljenosti postepeno smenjuje tačnijom vrednošću sve dok se eventualno ne dostigne optimalno rešenje. U oba algoritma, približna udaljenost do svakog čvora je uvek precenjena vrednost tačne udaljenosti, i zamenjuje se minimumom svoje stare vrednosti i dužine novootkrivenog puta. Međutim, Dejkstrin algoritam pohlepno bira čvor sa najmanjom težinom koji još uvek nije posećen, i ponavlja isti postupak na svim ostalim ivicama; u poređenju, Belman-Fordov algoritam jednostavno relaksira sve ivice, i to čini |V | − 1 puta, gde je |V | broj čvorova u grafu. U svakom novom ponavljanju, broj čvorova sa tačno izračunatom udaljenosti raste, odakle sledi da će eventualno svi čvorovi imati tačno izračunate udaljenosti. Ova metoda dopušta Belman-Fordovom algoritmu da se koristi na širu klasu ulaza od Dejkstrinog.

Belman-Ford se izvršava u vremenu O(|V|·|E|), gde su |V| i |E| brojevi čvorova i ivica.

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"

Dokaz korektnosti

Korektnost algoritma se može pokazati matematičkom indukcijom.

Lema. Nakon i ponavljanja for petlje:

• Ako Distance(u) nije beskonačno, onda je jednako dužini putanje od s do u;
• Ako postoji put od s do u sa najviše i ivica, onda Distance(u) nije veće od dužine najkraćeg puta od s do u sa najviše i ivica.

Dokaz. Za bazni slučaj indukcije, razmatrajmo i = 0 i trenutak pre nego što je for petlja pokrenuta po prvi put. U tom slučaju je, za početni čvor, source.distance = 0, što je tačno. Za ostale čvorove u važi u.distance = infinity, što je takođe tačno, zato što ne postoji put iz source do u sačinjen od 0 ivica.

U induktivnom koraku, prvo dokazujemo prvi korak. Razmatrajmo trenutak kada se udaljenost čvora menja sa v.distance := u.distance + uv.weight. Po induktivnoj hipotezi, u.distance je dužina nekog puta od source do u. onda je u.distance + uv.weight dužina puta od source do v koja prati put od source do u a onda ide do v.

Što se tiče drugog koraka, razmatrajmo najkraći put od source do u sa najviše i ivica. Neka je v čvor pre u na ovom putu. Onda, deo puta od source do v je najkraći put od source do v sa najviše i-1 ivica. Po induktivnoj hipotezi, v.distance posle i−1 iteracija petlje nije veća od dužine ovog puta. Odatle sledi da uv.weight + v.distance nije veća od dužine puta od s do u. U i-toj iteraciji, u.distance se poredi sa uv.weight + v.distance, i jednaka joj je ukoliko je uv.weight + v.distance bilo manje. Dakle, posle i iteracija, u.distance nije veće od dužine najkraćeg puta od source do u sa najviše i ivica.

Ukoliko nema ciklusa sa negativnom težinom, onda svaki najkraći put poseti svaki čvor najviše jednom, tako da se u trećem koraku ne može napraviti neko poboljšanje. Nasuprot tome, pretpostavimo da se ne može napraviti poboljšanje. onda za svaki ciklus sa čvorovima v[0], ..., v[k−1] važi,

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

Sumiranjem oko ciklusa, v[i].distance i v[i−1 (mod k)] distance se potiru, ostavljajući 0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

To jest, svaki ciklus ima nenegativnu vrednost.

Nalaženje negativnih ciklusa

Kada se algoritam koristi za pretragu najkraćeg puta, postojanje negativnih ciklusa je problem koji sprečava algoritam da pronađe tačan odgovor. Međutim, s obzirom da staje kada naiđe na negativni ciklus, Belman-Fordov algoritam se može koristiti u aplikacijama u kojoj je to cilj - na primer u tehnikama poništavanja ciklusa u analizi transportacionih mreža.

Primena u rutiranju

Distribuirana varijanta Belman-Fordovog algoritma se koristi u protokolima rutiranja na osnovu vektora udaljenosti, na primer, u RIP-u. Algoritam je distribuiran zato što uključuje neki broj čvorova (rutera) unutar autonomnog sistema, skupa IP mreža koje su uglavnom u vlasništvu nekog ISP-a. Sastoji se iz sledećih koraka:

1. Svaki čvor računa rastojanje između sebe i svih drugih čvorova unutar AS-a i skladišti ovu informaciju unutar tabele.
2. Svaki čvor šalje svoju tabelu susednim čvorovima.
3. Kada čvor primi tabelu od svojis suseda, on izračunava najkraću putanju do svih drugih čvorova i menja svoju tabelu ukoliko je došlo do nekih promena.

Glavne mane Belman-Fordovog algoritma u ovom okruženju su:

• Skaliranje se ne vrši dobro.
• Promene u topologiji mreže se ne odražavaju brzo, pošto se ispravke šire sa čvora na čvor.
• Problem brojenja do beskonačnosti (ukoliko usled neke greške dođe do toga da je neki čvor nedostižan iz nekog skupa drugih čvorova, ti čvorovi mogu da povećavaju svoje procene rastojanja do nedostižnog čvora).

Unapređenja

Belman-Fordov algoritam se može unaprediti u praksi (ali ne i u najgorem slučaju) uz posmatranje da, ukoliko se iteracija glavne petlje algoritma terminira bez pravljenja nekih promena, algoritam se može istog trenutka terminira, zato što naredne iteracije neće praviti izmene. Uz ovaj uslov, glavna petlja u nekim slučajevima ima mnogo manje od |V| − 1 iteracija, iako najgori slučaj algoritma ostaje nepromenjen.

Jen (1970) opisuje još dva unapređenja Belman-Fordovog algoritma za graf bez ciklusa negativne težine; opet, iako čine algoritam brži u praksi, ne menjaju njegov najgori slučaj od O(|V|*|E|). Njegovo prvo unapređenje smanjuje broj relaksacionih koraka koji su potrebni za svaku iteraciju algoritma. Ako čvor v ima udaljenost koja se nije promenila od poslednjeg puta kada su se ivice koje idu iz v relaksirale, onda nema potrebe relaksirati ivice iz v po drugi put. Na ovaj način, kako se broj čvorova sa tačnim udaljenostima povećava, broj ivica koje trebaju da se relaksiraju u svakoj iteraciji smanjuje, što vodi do konstantnog ušteđenja vremena za guste grafove.

Jenovo drugo unapređenje prvo dodeljuje arbitrarni linearni red svim čvorovima i onda particioniše skup svih čvorova na dva podskupova. Prvi podskup, E_f, sadrži sve ivice (v_i, v_j) takve da je i < j; drugi podskup, E_b, sadrži ivice (v_i, v_j) takve da je i > j. Svaki čvor je posećen redom v₁, v₂, ..., v_|V|, relaksirajući svaku ivicu koja ide od tog čvora iz E_f. Svaki čvor se onda posećuje redom v_|V|, v_|V|−1, ..., v₁, relaksirajući svaku ivicu koja ide iz čvora E_b. Svaka iteracija u glavnoj petlji algoritma, posle prve, dodaje barem dve ivice u skup ivica čije se relaksirane udaljenosti poklapaju sa tačnim najkraćim putem: jedna iz E_f i jedna iz E_b. Ova modifikacija smanjuje broj iteracija glavne petlje u najgorem slučaju sa |V| − 1 na |V|/2.

Još jedno unapređenje od strane Banistera i Epštajna (2012), zamenjuje arbitrarni linearni red čvorova korišćenih u Jenovom drugom unapređenju sa nasumičnom permutacijom. Ova promena čini da se najgori slučaj za Jenovo unapređenje (u kome čvorovi najkraćeg puta striktno alterniraju između dva podskupa E_f i E_b) veoma teško dogodi. Sa nasumičnom permutacijom redosleda čvorova, očekivana vrednost za broj iteracija potrebnih u glavnoj petnji je najviše |V|/3.

Literatura

Originalni izvori

• 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. str. 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. str. 41—47. arXiv:1111.5414 . Arhivirano iz originala (PDF) 4. 4. 2014. g. Pristupljeno 29. 5. 2013. 

Sekundarni izvori

• Bang-Jensen, Jørgen; Gutin, Gregory (2000). „Section 2.3.4: The Bellman-Ford-Moore algorithm”. Digraphs: Theory, Algorithms and Applications (First izd.). 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. str. 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 izd.). ISBN 978-0-201-36121-6. Arhivirano iz originala 31. 05. 2008. g. Pristupljeno 29. 05. 2013. 

Spoljašnje veze

• Open Source Java paket za rad sa grafovima i Belman-Fordovim algoritmom