Bellman-Fordov algoritem za iskanje najkrajših poti

Bellman-Fordov algoritem za iskanje najkrajših poti

Avtor: Maja Ban

OSNOVNI POJMI

Na začetku si poglejmo nekaj osnovnih pojmov, da nam bo v nadaljevanju bolj razumljivo.

GRAF je sestavljen iz vozlišč (točk) in povezav, ki povezujejo vozlišča. Matematična oznaka za graf je G:=(V,E), kjer je V množica vozlišč, E pa množica povezav. Graf je lahko usmerjen ali neusmerjen. Pri neusmerjenih grafih ne določimo smeri zato se lahko po povezavah premikamo v obe smeri. USMERJEN GRAF je, če ima vse povezave usmerjene. Iz enega vozlišča v drugo vozlišče se premikamo v smeri povezave.

(http://www2.nauk.si/files/723/1.jpg)

Slika prikazuje usmerjen graf

UTEŽEN GRAF je graf, kateri ima na povezavah uteži (teže, cene, dolžine). S tem povemo vrednost povezave. Uteži so lahko negativna ali pozitivna števila.

(http://www2.nauk.si/files/723/2.jpg)

Slika prikazuje usmerjen graf z utežjo

NAJKRAJŠA POT v grafu je tista pot, katera gre iz začetnega vozlišča v drugo vozlišče tako, da je vsota vseh uteži na povezavah najmanjša. Najkrajše poti od poljubnega začetnega vozlišča do vseh ostalih vozlišč grafa lahko predstavimo kot drevo, pravimo mu drevo najkrajših poti.

Poznamo več algoritmov za iskanje najkrajših poti, in sicer: Dijkstrov algoritem za iskanje najkrajše poti od začetnega vozlišča do ostalih vozlišč. Dolžine vseh povezav so pozitivne. Nato Bellman-Fordov algoritem za iskanje najkrajše poti od začetnega vozlišča do ostalih vozlišč tudi z negativnimi utežmi. Ter Floyd-Warshallov algoritem za iskanje najkrajših poti med vsemi pari vozlišč s poljubnimi utežmi.

ALGORITEM

BELLMAN-FORDOV ALGORITEM sta razvila ameriška matematika Richard Bellman in Lester Randolph Ford, Jr., po katerih je algoritem dobil ime. Algoritem poišče najkrajše poti od poljubnega začetnega vozlišča do vseh ostalih vozlišč v usmerjenem in uteženem grafu s poljubnimi utežmi (tudi negativne uteži). Na koncu za rezultat algoritma dobimo drevo najkrajših poti in teže na povezavah teh najkrajših poti. Algoritem sloni na dinamičnem programiranju. Je najhitrejši znan algoritem za splošne grafe (reši v polinomskem času).

Da bo algoritem deloval, sta potrebna pogoja, in sicer:

  1. Začetno vozlišče mora biti povezano z vsemi ostalimi vozlišči grafa, drugače ne moremo poiskati najkrajše poti iz začetnega vozlišča do vozlišča, ki ni povezano,
  2. Usmerjen in utežen graf brez negativnih ciklov, če graf vsebuje negativen cikel nas na to opozori.
  • Primer negativnega cikla:

    (http://www2.nauk.si/files/723/3.jpg)

Če seštejemo uteži med vozlišči A, B in C, bomo dobili negativno število, kar pomeni, da je to negativen cikel, 9+(-16)+(-4)=-11<0.

Časovna zahtevnost Bellman-Fordovega algoritma je O(|V||E|), (V je množica vozlišč, E pa množica povezav).

Nobena najkrajša pot nima več kot |V(G)|-1 povezav, kjer je |V(G)| število vozlišč grafa. Naredimo prav toliko korakov. Pri (ročnemu) reševanju lahko naredimo tudi manj korakov, ter dobimo že rešitev. Opazimo, da se vrednosti vozlišč ne spreminjajo več, prav tako se ne spreminjajo več predniki teh vozlišč. Tako lahko s pregledovanjem povezav zaključimo.

Uporaba algoritma: Uporablja se ga pri Google Maps, pri Rubikovi kocki, kjer računamo najkrajšo pot za sestavitev kocke v prvotno stanje. Algoritem se uporablja tudi v telekomunikacijah, robotiki, transportu, …

Uporaba pri Google Maps: Ko potujemo iz enega kraja v drugi kraj imamo veliko možnosti po kateri poti naj bi šli. Pri tem je več dejavnikov, ki jih upoštevamo, kot so npr.: razdalja, čas, cena goriva). Naš cilj je, da poiščemo najkrajšo pot med tema dvema krajema.

(http://www2.nauk.si/files/723/35.jpg)

Slika prikazuje zemljevid poti iz Ljubljane do Bleda.

Uporaba pri telekomunikaciji: Npr.: Nekdo z mobilnim telefonom pokliče neko osebo. Signal gre po najbližjih oddajnikih signala do ponudnika telekomunikacijskih storitev in nato po najbližjih oddajnikih signala do prejemnika klica.

Uporaba pri transportu: Npr.: Kamioniste zanima najkrajša pot iz enega kraja do drugega, da pripeljejo tovor tudi v najkrajšemu času do cilja.

IDEJA ALGORITMA

Najprej pogledamo najkrajše poti od začetnega vozlišča do najbližjih vozlišč. Nato se prestavimo na naslednje vozlišče in postopek ponovimo. V primeru, da je kakšna pot krajša kot v prejšnjemu koraku, jo zamenjamo z novo (krajšo pot). Postopek ponavljamo, dokler ne pridemo do zadnjega vozlišča. Pri tem je vseh korakov |V(G)|-1.

Opomba: S pomočjo psevdo kode naredimo |V(G)|-1 korakov in nič manj. Končno rešitev dobimo šele, ko gremo skozi zanko tolikokrat kot je korakov.

Če s tem postopkom ne dobimo najkrajše poti od začetnega vozlišča do ostalih vozlišč, potem graf vsebuje negativen cikel. To vemo zato, ker če bi naredili več kot |V(G)|-1 korakov, bi se s pregledovanjem povezav vrednost vozlišč zniževala in vrednosti bi postajale negativne, tako ne bi dobili najkrajše poti od začetnega vozlišča do ostalih vozlišč in v takšnemu primeru vsebuje graf negativen cikel.

VHODNI PODATKI:

  • Graf G(V,E), kjer je V množica vozlišč, E množica povezav,
  • Uteži na povezavah
  • Začetno vozlišče

IZHODNI PODATKI:

  • Tabela razdalj in očetov ali False

PSEVDO KODA:

  • Na začetku določimo:

    • Vrednost ostalih vozlišč nastavimo na ∞ (neskončno), (d[v] = ∞)
    • Na začetku prednikom vseh vozlišč nastavimo na 0, (pred[v] = 0)
  • Vrednost za začetno vozlišče nastavimo na 0, (d[r] = 0)
  • Gremo po vseh parih povezav [u,v] iz grafa G od začetnega vozlišča povezave u do končnega v (naredimo |V|-1 korakov) in ponavljamo:

    • Če velja, da je vsota vrednosti vozlišča u (d[u]) in utež med vozliščema u in v (oziroma cena med vozliščema u in v; w[u,v])manjša kot vrednost vozlišča v (d[v]); (d[u] + w[uv] < d[v]), potem: #če je kakšna pot krajša od prejšnje, jo zamenjamo z novo (krajšo)

      • Vozlišču v popravimo vrednost, (d[v] = d[u] + w[uv])
      • Vozlišču v popravimo prednika, (pred[v] = u)
  • Preverimo, da nimamo negativen cikel v grafu

    • Če velja d[u] + w[uv] < d[v], potem:

      • Vrnemo False
  • Vrnemo True

UPORABA BELLMAN-FORDOVEGA ALGORITMA NA GRAFU

Za primer vzemimo graf s šestimi vozlišči A, B, C, D, E, F in usmerjene povezave z utežmi (tudi negativnimi).

(http://www2.nauk.si/files/723/4.jpg)

Na začetku označimo začetno vozlišče z 0, ostala vozlišča pa z neskončno (∞). Ostala vozlišča označimo z neskončno, ker iz začetnega vozlišča še nismo določili nobene poti do ostalih vozlišč (nismo še začeli s pregledovanjem povezav).

(http://www2.nauk.si/files/723/5.jpg)

Pri tem si bomo pomagali s tabelo, v katero bomo vpisovali vrednosti vozlišč in njihove prednike.

(http://www2.nauk.si/files/723/6.jpg)

Sedaj moramo zapisati vse povezave med vozlišči v grafu in po takemu vrstnemu redu jih bomo tudi pregledovali.

(http://www2.nauk.si/files/723/7.jpg)

OPOMBA: Vrednost pri vozlišču je ocena najkrajše poti do trenutnega vozlišča. Vozlišče pa je trenutno vozlišče grafa.

(http://www2.nauk.si/files/723/34.jpg)

1. korak:

  • preverimo povezavo A → B: Vzamemo vrednost vozlišča A, katera je 0 in ji prištejemo vrednost povezave med vozliščema A in B. To je utež te povezave, katera je 2. Dobimo 0+2=2 (2 je nova dobljena vrednost za vozlišče B), kar je manjše od trenutne vrednosti vozlišča B (manjše od ∞). Zato dobi vozlišče B novo vrednost, 2 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča B).
(http://www2.nauk.si/files/723/8.jpg)

Tako v grafu spremenimo vozlišču B vrednost na 2. Prav tako spremenimo tudi v tabeli vrednost vozlišča B in prednik.

  • preverimo povezavo A → E: Vzamemo vrednost vozlišča A, to je 0 in vrednost povezave med vozliščema A in E, katera je 3. Ko seštejemo 0+3,dobimo 3 (3 je nova dobljena vrednost za vozlišče E), kar je manjše od trenutne vrednosti vozlišča E (manjše od ∞). Zato dobi vozlišče E novo vrednost, 3.
(http://www2.nauk.si/files/723/9.jpg)
  • preverimo povezavo B → C: Sedaj vzamemo vrednost vozlišča B, katera je 2 in vrednost povezave med vozliščema B in C, katera je 9. Nato vrednosti seštejemo 2+9=11 (11 je nova dobljena vrednost za vozlišče C). Vidimo, da je 11 manjše od trenutne vrednosti vozlišča C, ki je ∞. Zato to vozlišče dobi novo vrednost 11.
(http://www2.nauk.si/files/723/10.jpg)
  • preverimo povezavo C → A: Vrednosti vozlišča C prištejemo vrednost povezave med vozliščema C in A. Dobimo, da je 11+6=17 (17 je nova dobljena vrednost za vozlišče A), kar je večje od trenutne vrednosti vozlišča A, katera je 0. Zato vozlišče A ne dobi nove vrednosti, ostane nespremenjen.
(http://www2.nauk.si/files/723/11.jpg)
  • preverimo povezavo C → D: Vzamemo vrednost vozlišča C in mu prištejemo vrednost povezave med vozliščema C in D. Dobimo, da je 11+7=18 (18 je nova vrednost za vozlišče D),kar je manjše od trenutne vrednosti vozlišča D (manjše od ∞). Vozlišče D dobi novo vrednost, katera je 18.
(http://www2.nauk.si/files/723/12.jpg)
  • preverimo povezavo D → A: Ko vrednosti vozlišča D prištejemo vrednost povezave med vozliščema D in A, dobimo, da je 18+5=23 (23 je nova dobljena vrednost za vozlišče A) večje od trenutne vrednosti vozlišča A, katera je 0. V temu primeru ostane vrednost vozlišča A nespremenjena.
(http://www2.nauk.si/files/723/13.jpg)
  • preverimo povezavo D → F: Vrednosti vozlišča D prištejemo vrednost povezave med vozliščema D in F. Seštejemo ti vrednosti in dobimo 18+2=20 (20 je nova dobljena vrednost za vozlišče F), kar je manjše od trenutne vrednosti vozlišča F (manjše od ∞). Zato vrednost vozlišču F spremenimo na 20.
(http://www2.nauk.si/files/723/14.jpg)
  • preverimo povezavo E → C: Vrednost vozlišča E je v temu primeru 3 in ji prištejemo vrednost povezave med vozliščema E in C, ki je enaka -4. Ko seštejemo vrednosti 3+(-4)=-1 (-1 je nova dobljena vrednost za vozlišče C)dobimo, da je dobljena vrednost manjša od trenutne vrednosti vozlišča C, ki je 11. Zato vozlišču C spremenimo vrednost na -1 (-1 predstavlja oceno najkrajše poti do trenutnega vozlišča - do vozlišča C).
(http://www2.nauk.si/files/723/15.jpg)
  • preverimo povezavo E → D: Tudi v temu primeru, ko vrednosti vozlišča E prištejemo vrednost povezave med vozliščema E in D, dobimo, da je 3+(-4)=-1 (to je nova dobljena vrednost za vozlišče D) manjše od trenutne vrednosti vozlišča D, ki je 18. Zato vozlišču D zamenjamo novo vrednost, katera bo -1.
(http://www2.nauk.si/files/723/16.jpg)
  • preverimo povezavo F → B: Vzamemo vrednost vozlišča F, to je 20 in vrednost povezave med vozliščema F in B, to je 1. Ko seštejemo ti vrednosti, dobimo 21 (21 je nova dobljena vrednost za vozlišče B). Sedaj to vrednost primerjamo s trenutno vrednostjo vozlišča B, katera je enaka 2. Vidimo, da je 21 večje od 2, zato vozlišče B ohrani manjšo vrednost, ki je 2 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča B).
(http://www2.nauk.si/files/723/17.jpg)
  • preverimo povezavo F → E: Vrednosti vozlišča F prištejemo vrednost povezave med vozliščema F in E. Ko seštejemo vrednosti dobimo, da je 20+6=26 (to je nova dobljena vrednost za vozlišče E), kar pomeni, da je ta vrednost večja od trenutne vrednosti vozlišča E, ki je 3. Tako vozlišče E ohrani svojo vrednost.
(http://www2.nauk.si/files/723/18.jpg)

Sedaj smo prvi korak zaključili, saj smo vsako povezavo obiskali enkrat. Trenutno stanje na grafu po 1. koraku:

(http://www2.nauk.si/files/723/19.jpg)

Iz grafa lahko vidimo, da je najkrajša pot od vozlišča A do B vredna 2 enoti, od A do E je vredna 3 enote, od A do C je vredna -1 enot, od A do D je vredna -1 enot in od A do F je vredna 20 enot.

Nadaljujemo z 2. korakom. Povezave pregledujemo po istemu vrstnemu redu kot prej.

UPORABA BELLMAN-FORDOVEGA ALGORITMA NA GRAFU

2. korak:

  • Primerjamo povezavo A → B: Vzamemo vrednost vozlišča A in vrednost povezave med vozliščema A in B. Ko vrednosti seštejemo dobimo, da je seštevek (to je nova dobljena vrednost za vozlišče B) vrednosti enak trenutni vrednosti vozlišča B. Vrednost vozlišču B nič ne spremenimo, saj sta vrednosti enaki.
  • Primerjamo povezavo A → E: Ko vrednosti vozlišča A prištejemo vrednost povezave med vozliščema A in E, dobimo, da je ta vrednost enaka vrednosti vozlišču E. Vrednost vozlišča E ostane nespremenjena.
  • Primerjamo povezavo B → C: Vzamemo vrednost vozlišča B, ki je enaka 2 in vrednost povezave med vozliščema B in C, ki je 9. Ko vrednosti seštejemo, dobimo 11 (to je nova dobljena vrednost za vozlišče C), kar je večje od trenutne vrednosti vozlišča C, ki je -1. Zato vozlišče C ohrani vrednost -1 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča C).
  • Primerjamo povezavo C → A: Seštejemo vrednost vozlišča C in vrednost povezave med vozliščema C in A. Dobimo, da je -1+6=5 (to je nova dobljena vrednost za vozlišče A) in to je večje od trenutne vrednosti vozlišča A, ki je 0. Zato vrednost vozlišča A ostane nespremenjena.
  • Primerjamo povezavo C → D: Vzamemo vrednost vozlišča C in ji prištejemo vrednost povezave med vozliščema C in D. dobimo, da je -1+7=6 in to je večje od trenutne vrednosti vozlišča D, ki je -1, zato vrednost vozlišča D ostane nespremenjena.
  • Primerjamo povezavo D → A: Vrednosti vozlišča D prištejemo vrednost povezave med vozliščema D in A. Dobimo, da je -1+5=4, kar je večje od trenutne vrednosti vozlišča A, ki je 0. To pomeni, da vozlišče A ohrani vrednost 0 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča A).
  • Primerjamo povezavo D → F: Vzamemo vrednost vozlišča D in vrednost povezave med vozliščema D in F. Vrednosti seštejemo in dobimo, da je -1+2=1, kar je manjše od trenutne vrednosti vozlišča F, ki je 20. Zato vozlišče F dobi novo vrednost 1 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča F).
(http://www2.nauk.si/files/723/20.jpg)
  • Primerjamo povezavo E → C: Vrednosti vozlišča E prištejemo vrednost povezave med vozliščema E in C. Ko vrednosti seštejemo, dobimo, da je 3+(-4)=-1, kar je enako trenutni vrednosti vozlišča C. Vozlišče C ohrani vrednost -1.
  • Primerjamo povezavo E → D: Vzamemo vrednosti vozlišča E, to je 3 in vrednost povezave med vozliščema E in D, to je -4. Vrednosti seštejemo in dobimo, da je 3(-4)=-1 (to je nova dobljena vrednost za vozlišče D), kar je ravno trenutna vrednost vozlišča D. Zato vrednost vozlišča D ostane nespremenjena.
  • Primerjamo povezavo F → B: Vzamemo vrednost vozlišča F, ki je 1 in vrednost povezave med vozliščema F in B, to je 1. Vrednosti seštejemo 1+1=2 in to je enako trenutni vrednosti vozlišča B. Tudi vozlišče B ostane nespremenjeno.
  • Primerjamo povezavo F → E: Vzamemo vrednost vozlišča F, ki je 1 in vrednost povezave med vozliščema F in E, ki je 6. Ko vrednosti seštejemo dobimo, da je 1+6=7, kar je večje od trenutne vrednosti vozlišča E, ki je 3 (to število predstavlja oceno najkrajše poti do trenutnega vozlišča E). Vrednost vozlišča E ostane nespremenjena.

Po zaključenemu 2. koraku, si poglejmo trenutno stanje na grafu:

(http://www2.nauk.si/files/723/21.jpg)

Iz grafa lahko vidimo, da je najkrajša pot od vozlišča A do B vredna 2 enoti, od A do E je vredna 3 enote, od A do C je vredna -1 enot, od A do D je vredna -1 enot in od A do F je vredna 1 enoto.

Nadaljujemo z naslednjim korakom.

3. korak:

  • Primerjamo povezavo A → B: Vzamemo vrednost vozlišča A in vrednost povezave med vozliščema A in B. Ko vrednosti seštejemo vidimo, da dobimo enako vrednost, kot je trenutna vrednost vozlišča B. Vrednost vozlišča B ostane v temu primeru nespremenjena.
  • Primerjamo povezavo A → E: Vzamemo vrednost vozlišča A in vrednost povezave med vozliščema A in E. Vrednosti seštejemo in dobimo, da je 0+3=3. Vidimo, da je vsota vrednosti enaka trenutni vrednosti vozlišča E, zato vrednost pri temu vozlišču ostane enaka.
  • Primerjamo povezavo B → C: Ko seštejemo vrednost vozlišča B in vrednost povezave med vozliščema B in C, dobimo 2+9=11, kar je večje od trenutne vrednosti vozlišča C, ki je -1. Zato vozlišču C ne spremenimo vrednosti.
  • Primerjamo povezavo C → A: Vzamemo vrednost vozlišča C in vrednost povezave med vozliščema C in A. Njuni vrednosti seštejemo in dobimo, da je -1+6=5 večje od trenutne vrednosti vozlišča A, ki je 0. Zato vozlišče A ohrani svojo trenutno vrednost, saj je manjša od te dobljene vrednosti.
  • Primerjamo povezavo C → D: Vzamemo vrednost vozlišča C in vrednost povezave med vozliščema C in D. Vrednosti seštejemo in dobimo -1+7=6, kar je večje od trenutne vrednosti vozlišča D, ki je -1. Vozlišču D ne spremenimo vrednosti, ker je -1 manjša vrednost.
  • Primerjamo povezavo D → A: Ko seštejemo vrednost vozlišča D in vrednost povezave med vozliščema D in A dobimo, da je -1+5=4. Vsota vrednosti je večja od trenutne vrednosti vozlišča A, zato to vozlišče ohrani svojo trenutno vrednost.
  • Primerjamo povezavo D → F: Vzamemo vrednost vozlišča D in vrednost povezave med vozliščema D in F. Ko ju seštejemo dobimo, da je -1+2=1, kar je enako trenutni vrednosti vozlišča F, zato ne spremenimo vrednosti pri temu vozlišču.
  • Primerjamo povezavo E → C: Vzamemo vrednost vozlišča E in vrednost povezave med vozliščema E in C. Vrednosti seštejemo in dobimo 3+(-4)=-1 in ta vrednost je enaka trenutni vrednosti vozlišča C, zato vrednosti pri vozlišču ne spreminjamo.
  • Primerjamo povezavo E → D: Vzamemo vrednost vozlišča E in vrednost povezave med vozliščema E in D. Vrednosti seštejemo 3+(-4)=-1 in vidimo, da je ta vrednost enaka trenutni vrednosti vozlišča D, zato ostane vrednost vozlišča D nespremenjena.
  • Primerjamo povezavo F → B: Vzamemo vrednost vozlišča F in vrednost povezave med vozliščema F in B. Ko vrednosti seštejemo dobimo, da je 1+1=2, kar je enako trenutni vrednosti vozlišča B. Vozlišče B ohrani svojo vrednost.
  • Primerjamo povezavo F → E: Vzamemo vrednost vozlišča F in vrednost povezave med vozliščema F in E. Ko vrednosti seštejemo dobimo, da je 1+6=7, kar je večje od trenutne vrednosti vozlišča E, ki je 3. Zato vozlišče E ohrani svojo vrednost.

Kot vidimo, pri 3. koraku ne pride do nobene spremembe pri vrednosti vozlišč in prednikov. V takemu primeru lahko zaključimo s pregledovanjem, saj ko bi nadaljevali s pregledovanjem nebi prišlo več do sprememb. Na spodnjemu grafu je prikazano stanje po 3. koraku.

(http://www2.nauk.si/files/723/22.jpg)

Najkrajša razdalja iz vozlišča A v B je vredna 2 enoti, iz A v C je vredna -1 enot, iz A v D je vredna -1 enot, iz A v E je vredna 3 enote, iz A v F je vredna 1 enoto.

Na koncu še preverimo, da nimamo negativnega cikla tako, da gremo skozi vse povezave in če velja neenakost d[u]+w[uv]<d[v] (začetnemu vozlišču u prištejemo ceno povezave med vozliščema u in v, in če je ta seštevek manjši od končnega vozlišča v), potem graf vsebuje negativen cikel. V našemu primeru graf ne vsebuje negativnega cikla.

Poglejmo še vrednosti najkrajših poti med začetnim vozliščem A in ostalimi vozlišči. Med vozliščema:

  • A in B je razdalja 2 (direktna povezava)
  • A in E je razdalja 3 (direktna povezava)
  • A in C je razdalja -1 (povezava gre skozi vozlišče E)
  • A in D je razdalja -1 (povezava gre skozi vozlišče E)
  • A in F je razdalja 1 (povezava gre skozi vozlišči E in D)

Na koncu dobimo drevo najkrajših poti:

(http://www2.nauk.si/files/723/23.jpg)

UPORABA BELLMAN-FORDOVEGA ALGORITMA NA GRAFU Z NEGATIVNIM CIKLOM

Za primer vzemimo graf prav tako s šestimi vozlišči A, B, C, D, E, F in usmerjene povezave z utežmi (tudi negativnimi).

(http://www2.nauk.si/files/723/24.jpg)

Tudi pri temu primeru izpišemo povezave kar v tabelo.

(http://www2.nauk.si/files/723/25.jpg)

Po istemu postopku kot smo rešili prejšnji primer, rešimo tudi ta primer.

Za začetno vozlišče si izberemo A, ki ga označimo z 0, ostala vozlišča označimo z ∞.

(http://www2.nauk.si/files/723/26.jpg)

Ko bomo pregledovali vozlišča, bomo opazili, da vrednosti vozlišč postajajo negativne. V primeru, če bo začetno vozlišče dobilo negativno vrednost lahko zaključimo s pregledovanjem.

Pri temu primeru dobimo negativen cikel (to je zaporedje vozlišč, ki se vrnejo v začetno vozlišče in vsota uteži je negativna vrednost). Vrednosti vozlišč postajajo negativne.

Opomba: Negativni cikli, ki imajo vsoto uteži negativno, so dosegljivi iz začetnega vozlišča (obstaja pot od začetnega vozlišča do katerega koli vozlišča negativnega cikla).

Stanje na grafu po 1. koraku:

(http://www2.nauk.si/files/723/27.jpg)

Če nadaljujemo s pregledovanjem, bomo opazili, da se vrednost vozlišč znižuje za toliko kot je vrednost negativnega cikla. To lahko vidimo v naslednjemu koraku (v 2. koraku). Ko seštejemo uteži negativnega cikla dobimo 1+(-8)+(-2)=-9, kar pomeni, da se vrednosti vozlišč znižujejo za -9.

(http://www2.nauk.si/files/723/28.jpg)

V primeru, da bi nadaljevali pregledovanje bi se vsaka vrednost vozlišča zniževala za -9 in bi vsakič dobili še cenejšo pot. Nikoli nebi dobili najcenejše poti.

FILM

KVIZ

1. Kaj poišče Bellman-Fordov algoritem?

Najkrajšo pot od poljubnega začetnega vozlišča do vseh ostalih vozlišč v neusmerjenem in uteženem grafu s poljubnimi utežmi (tudi negativnimi).
Najdaljšo pot od poljubnega začetnega vozlišča do vseh ostalih vozlišč v usmerjenem in uteženem grafu s poljubnimi utežmi (tudi negativnimi).
Najkrajšo pot od poljubnega začetnega vozlišča do vseh ostalih vozlišč v usmerjenem in uteženem grafu s poljubnimi utežmi (tudi negativnimi).

Odgovor je pravilen!

Naprej

Odgovor je napačen!

Poskusi ponovno!

KVIZ

2. Ali ima najkrajša pot grafa |V(G)| povezav?

Da
Ne

Odgovor je pravilen! Najkrajša pot ima povezav!

Naprej

Odgovor je napačen!

Zapri!

KVIZ

3. Katera dva pogoja sta potrebna, da bo algoritem deloval?

Preveri!

Odgovor je pravilen!

Naprej!

Odgovor je napačen!

Poskusi ponovno!

KVIZ

4. Reši primer! Za začetno vozlišče izberemo A. Katera slika izmed danih prikazuje drevo najkrajših poti za dani graf?

(http://www2.nauk.si/files/723/29.jpg)
(http://www2.nauk.si/files/723/31.jpg)
(http://www2.nauk.si/files/723/32.jpg)
(http://www2.nauk.si/files/723/30.jpg)

Odgovor je pravilen!

Naprej

Odgovor je napačen!

Poskusi ponovno!

KVIZ

5. Za koliko bi se pri danemu grafu z negativnim ciklom pri nadaljnjemu pregledu vozlišč zniževala vrednost vozlišč, če izberemo začetno vozlišče A?

(http://www2.nauk.si/files/723/33.jpg)

Preveri!

Right

Odgovor je pravilen!

Naprej!

Wrong

Odgovor je napačen!

Poskusi ponovno!

VIRI

Internetne povezave:

  • http://www.fmf.uni-lj.si/~juvan/Racunalnistvo3/0708/gradivo/najkrajse_poti.pdf
  • http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
  • http://wiki.fmf.uni-lj.si/wiki/Bellman-Fordov_algoritem

Zapiski:

  • Zapiski iz predmeta Optimizacija
  • Zapiski iz predmeta Diskretno modeliranje

Knjige:

  • Algoritmi in podatkovne strukture II, Igor Kononenko, Marko Robnik Šikonja, FRI, 2004
  • Osnovni algoritmi, Boštjan Vilfan, FRI
  • Uvod v teorijo grafov, Robin J. Wilson / John J. Watkins, DMFA, 1997
  • Diskretno dinamično programiranje, Alojzij Vadnal, Državna založba Slovenije, Ljubljana 1976
  • Podatkovne strukture in algoritmi, Jernej Kozak, DMFA, 1997
0%
0%