Bellman-Fordov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Bellman-Fordov algoritem poišče najkrajše poti v usmerjenem in uteženem grafu s poljubnimi utežmi. Če ima graf samo pozitivne utežmi, raje uporabimo Dijkstrov algoritem, ki reši isti problem v krajšem času.

Imamo usmerjen in utežen graf G. Predpostavimo, da graf ne vsebuje negativnega cikla. Potem nobena najkrajša pot nima več kot | V(G) | − 1 povezav, kjer je | V(G) | število vozlišč grafa. Naredimo prav toliko korakov. Algoritem sloni na dinamičnem programiranju. Po i-tem koraku poznamo najkrajše poti med vozlišči, ki nimajo več kot i povezav. Na koncu preverimo, ali obstaja negativen cikel.

Opis algoritma


Imamo graf G = (V,E), izhodiščno točko s in uteži na povezavah w. Algoritem nam vrne vrednost true, drevo najkrajših poti π, kjer je π[u] prednik vozlišča u, in njihove teže d, kjer je d[u] teža najkrajše poti od s do u, pri pogoju, da ni negativnega cikla dosegljivega iz s. Sicer nam algoritem vrne vrednost false.

Na začetku nastavimo π[u] = nil, d[u] = ∞, d[s]=0 (ker še ni nobene poti od s do vseh ostalih točk). Pogledamo najkrajše poti do najbližnjih točk od s. Prestavimo se na naslednjo točko. Zopet pogledamo najkrajše poti do najbližnjih točk razen s. Če je kakšna pot krajša kot je bila pri prejšnjem koraku, jo zamenjamo z novo (krajšo). Ponavljamo, dokler ne pridemo do zadnje točke. Teh korakov je | V(G) | − 1. Na vsakem koraku se relaksirajo vse povezave grafa natanko enkrat. Na koncu še preverimo, če obstaja negativen cikel.

Ta opis ponazorimo v psevdokodi:

//korak 1: inicializirati graf
za vsako točko v in ostale točke
  če je v koren, potem je razdalja d(v) = 0
  sicer d(v) = ∞
  Π(v) = 0
//korak 2: iskanje najkrajših poti
for od 1 do število točk
 za vsako povezavo (u,v) velja
   u = začetna točka
   v = končna točka 
   if d(v) > d(u) + (u,v)
      d(v) = d(u) + (u,v)
      Π(v) = u
//korak 3: preverimo, če imamo negativen cikel
za vsako povezavo (u,v) velja
   u = začetna točka
   v = končna točka 
   if d(v) > d(u) + (u,v)
      napaka "graf vsebuje negativen cikel"

Časovna zahtevnost algoritma je O( | V | | E | ).

Relaksacija

Relaksacija nad povezavo (u,v) preveri, če lahko zmanjšamo težo najkrajše poti od s do v (d[v]) tako, da najkrajši poti od s do u (d[u]) dodamo povezavo (u,v).

  1. RELAX(u,v,w)
  2. if d[v] > d[u] + w(u,v) then
  3. d[v] = d[u] + w(u,v)
  4. π[v] = u

Shema algoritma

  1. BELLMAN-FORD(G,s,w)
  2. for each u\inV(G) do
  3. d[u] = ∞
  4. π[u] = nil
  5. d[s]=0
  6. for i=1 to |V(G)|-1 do
  7. for each (u,v)\inE(G) do
  8. RELAX(u,v,w)
  9. for each (u,v)\inE(G) do
  10. if d[v] = d[u] + w(u,v) then
  11. return false
  12. return true


Primeri

Primer 1

Imamo dan graf. Poiščemo najkrajše poti od točke a do ostalih točk!

Slika:Primer_01.JPG

1.korak

Iz točke a iščemo najkrajše poti do točk b in c.

Slika:Primer_02.JPG

2.korak

Tokrat gledamo iz točke b. Poiščemo najkrajše poti do točk c in d.

Slika:Primer_03.JPG

Izberemo pot a-->b-->c dolžine 3 namesto poti a-->c dolžine 5.

3.korak

Iz točke c iščemo najkrajše poti do d in e.

Slika:Primer 04.JPG

Izberemo pot a-->b-->c-->d dolžine 6 namesto poti a-->b-->d dolžine 9.

4.korak

Iz točke d iščemo najkrajšo pot do e.

Slika:Primer_05.JPG

Izberemo pot a-->b-->c-->d-->e dolžine -2 namesto poti a-->b-->c-->e dolžine 5.

Dobili smo graf najkrajših poti. V grafu ni nobenega negativnega cikla.

Primer 2

Imamo dan graf, ki je podoben iz Primera 1. Poiščemo najkrajše poti od točke a do ostalih točk!

Slika:Primer 001.JPG

1.korak

Iz točke a poiščemo najkrajše poti do točk b in c.

Slika:Primer 002.JPG

2.korak

Iz točke b poiščemo najkrajšo pot do točke c.

Slika:Primer 003.JPG

3.korak

Iz točke c iščemo najkrajše poti do točk d in e.

Slika:Primer 004.JPG

4.korak

Iz točke d iščemo najkrajše poti do točk b in e.

Slika:Primer 005.JPG

Kot vidimo, smo dobili negativen cikel, zato to ni graf najkrajših poti.


Primer 3

Imamo dan graf G in na njem iščemo najkrajše poti od točke r.

Slika:Primer 0001.JPG

Že po nekaj korakih dobimo sliko

Slika:Primer 0002.JPG

Ko naredimo naslednji korak, in sicer iščemo nakrajšo pot iz točke b v točko c dobimo sliko

Slika:Primer 0003.JPG

Vidimo, da dobimo negativen cikel vreden -3. Povezave r-->c ne smemo odstraniti, saj iz točke r začnemo delati vse korake. Če pa bi jo odstranili, potem ne bi vedeli, kam naj s to točko, in spremeni se nam izhodišče. Mi pa želimo, da je izhodišče točka r.

Ugotovimo, da nam algoritem vrne false, ne vrne nam pa grafa najkrajših poti, ker smo po algoritmu dobili negativen cikel.

Viri

Osebna orodja