Najprej si poglejmo opredelitve osnovnih pojmov, ki so povezani z omenjeno temo in bodo ključnega pomena pri nadaljnjem razumevanju, in sicer gre za opredelitev pojma grafa, usmerjenega grafa, najkrajše poti ter algoritma.

GRAF je sestavljen iz množice točk (oz. vozlišč), ki so med seboj povezane s povezavami.
Pišemo: G(V,E), kjer je V množica točk, E pa množica povezav. Povezavo lahko predstavimo kot par vozlišč, ki ju ta povezava med seboj povezuje, pri tem najprej navedemo začetno nato pa končno vozlišče.

V osnovnem grafe razdelimo v dve skupini, in sicer na usmerjene in neusmerjene. Pri usmerjenih grafih gre za to, da povezavam določimo smeri (katere prikažemo s puščicami), v katerih se lahko po grafu premikamo, pri neusmerjenem pa ne, zato se lahko premikamo v obeh smereh. V nadaljevanju bodo za nas pomembnejši usmerjeni grafi.

UTEŽEN GRAF je graf, kateremu povezavam dodamo oziroma priredimo uteži (oz. vrednosti, cene). Z utežjo povemo, koliko je vredna povezava med danima točkama. Teže so lahko pozitivna ali negativna števila.

V nadaljevanju nas bodo zanimali predvsem usmerjeni uteženi grafi (lahko imajo tudi negativne uteži), zato si poglejmo primer takega grafa:

Slika1: Primer grafa

• Množica vozlišč: V={A, B, C, D}
• Množica povezav E={(A, B), (A, C), (A, D), (B, D), (C, D)}
• S puščicami so označene (usmerjene) povezave
• Številke na povezavah določajo uteži (cene) povezav

NAJKRAJŠA POT je tista pot, ki predstavlja najmanjšo (oz. najcenejšo) vsoto povezav med vozlišči grafa.

Z iskanjem najkrajših poti se ukvarja več algoritmov, nam znani so predvsem:

• Bellman-Fordov algoritem,
• Dijkstrin algoritem ter
• Floyd-Warshallov algoritem.

Bellman – Fordov ter Dijkstrin algoritem poiščeta najkrajše poti iz neke točke do vseh ostalih točk, razlika med njima je v tem, da so pri Bellman – Fordovem algoritmu na povezavah dovoljene tudi negativne uteži, pri Dijkstrinem pa so uteži izključno pozitivne. Floyd – Warshallov algoritem pa v danem grafu poišče najkrajše poti med vsemi pari točk, tudi tu so lahko uteži pozitivne ali negativne. Od tu naprej se bomo osredotočili na Bellman – Fordov alogritem.

ALGORITEM je nekakšno navodilo, kako rešiti nek problem. Po navadi je zapisan kot seznam oziroma zaporedje korakov, ki nas privedejo do končne rešitve problema. Algoritem dobi na začetku določene podatke, vrne pa rezultat.

DREVO NAJKRAJŠIH POTI je tako vpeto drevo, da je razdalja med začetnim (izhodiščnim) vozliščem in vsemi ostalimi vozlišči minimalna.

Bellman – Fordov algoritem sta razvila ameriška matematika Richard Bellman in Lester Randolph Ford, Jr., po katerih je algoritem tudi dobil ime.

S pomočjo Bellman – Fordovega algoritma poiščemo najkrajšo pot od izhodiščne točke do vseh ostalih točk v usmerjenem uteženem grafu. Algoritem dovoljuje na povezavah poleg pozitivnih tudi negativne uteži. Kot rezultat algoritma dobimo drevo najkrajših poti in njihove teže

Potrebna POGOJA za delovanje algoritma:

• graf ne vsebuje negativnih ciklov, dosegljivih iz izhodiščne točke, v primeru da jih potem rešitev ne obstaja. Kajti če bi graf vseboval nek negativen cikel, potem bi se lahko po tem ciklu sprehodili večkrat in tako vseskozi zmanjševali vrednosti vozliščem (tako bi vsakič ko bi šli čez cikel dobili še neko cenejšo pot, nikoli nebi dobil najcenejše).
  Primer negativnega cikla vidimo na spodnji sliki. Negativni cikel določajo točke A-E-A (na sliki označene z rdečimi puščicami), vrednost uteži v ciklu je: 5 + 2 - 9 = -2 < 0

Slika2: Primer negativnega cikla v grafu

• začetno vozlišče mora biti povezano z vsemi ostalimi vozlišči grafa, kajti v primeru da z nekim vozliščem ni povezano (recimo da z vozliščem t, ki je element grafa), potem ne moremo poiskati najkrajše poti iz začetnega vozlišča do t

• v algoritmu vozliščem grafa določimo vrednosti, ki jih bomo označevali z d[v]. Vrednost posameznega vozlišča predstavlja oddaljenost od izhodiščne točke do tega vozlišča
• posamezen korak algoritma se zaključi, ko v njem pregledamo vsako povezavo grafa natanko enkrat
• na vsakem koraku bomo pregledovali povezave (razen povezave, ki vodijo do izhodiščnega vozlišča s) in poskušali zmanjšati vrednost vozlišč ter tako poiskati najkrajše poti od s do vseh ostalih točk
• dogovorimo se, da bomo prednike vozlišč označevali s π (prednik je tiso vozlišče, ki je predhodno od trenutnega vozlišča)ter da bomo ceno med vozliščema u in v označili z w[u,v]
• z izvajanjem algoritma se ustavimo na koraku, ko preverimo vse povezave grafa in ne ugotovimo več nobene spremembe (zmanjšanja vrednosti vozlišča). Največje število potrebnih korakov bo V-1, kjer je V število vozlišč grafa G

• poiskati najkrajšo pot od izhodiščnega, do vseh ostalih vozlišč v grafu
• na določenem koraku vemo, kakšna bo najkrajša pot od izhodiščne točke do ostalih točk, če bomo upoštevali določene povezave
• v primeru da bomo v tekočem koraku, s tem ko bomo upoštevali povezavo [u,v] zmanjšali težo najkrajše poti od izhodiščnega vozlišča do vozlišča v, potem vozlišču v zmanjšamo vrednost, povezavo od u do v pa dodamo najkrajši poti (od izhodiščnega vozlišča do u)
• algoritem tudi zazna negativne cikle v grafu in nas na to opozori (najkrajše poti v grafu ni mogoče določiti)

VHODNI PODATKI:

• Graf G(V,E), kjer je V množica vozlišč, E pa množica povezav
• Cene povezav oz. uteži na povezavah
• Izhodiščno (začetno) vozlišče s

• na začetku določimo:

  • najkrajše razdalje od izhodiščnega vozlišča s do vseh ostalih vozlišč v iz grafa G so enake neskončno (ker iz točke s še nismo določili nobene poti do ostalih točk):

    • d[v] = ∞

  • začetna vrednost izhodiščnega vozlišča s je 0:

    • d[s] = 0

  • prednikom vsem vozlišč v iz grafa G določimo vrednost NULL:

    • π[v] = NULL

• vzamemo vse pare povezav [u,v] iz grafa G, kjer je u začetno vozlišče povezave, v pa končno in ponavljamo:

  • če je vrednost vozlišča v večja kot vsota vrednosti v vozlišču u in cena med vozliščema u in v, torej če velja neenakost d[v] > d[u] + w[u,v] potem:

    • vozlišču v popravimo vrednost:

      • d[v] = d[u] + w[u,v]

    • vozlišču v popravimo prednika:

      • π [v] = u
    • v drevo najkrajših poti dodamo povezavo [u,v]
    • če je v drevesu najkrajših poti že kaka povezava do vozlišča v jo iz drevesa odstranimo

• na koncu preverimo še, da ni v grafu negativnega cikla

  • če tudi po V-1 korakih za kaktero od povezav [u,v] še vedno velja d[v]>d[u]+w[u,v] je v grafu nek negativen cikel:

    • rešitev ne obstaja

Dan imamo graf na 6 vozliščih: A, B, C, D, E in F, kot vidimo na spodnji sliki. Iščemo najkrajše poti od točke C do vseh ostalih točk grafa.

Slika3: Začetni problem

Dogovorimo se, da bomo dolžine oz. ocene najkrajših poti za vsako vozlišče pisali ob vozlišču (na slikah označene z zeleno) , kot vidimo na spodnjem primeru:

Slika4: Primer oznake vrednosti vozišča

Najprej vozliščem nastavimo začetne vrednosti:

d[A] = 0
d[B] = d[C] = d[D] = d[E] = d[F] = ∞
π[A] = π [B] = π[C] = π[D] = π[E] = π[F] = NULL

Poglejmo si kako sedaj zgleda začetni graf (ko smo vozliščem določili vrednosti):

Slika5: Graf z začetnimi vrednostmi vozlišč

Zapišimo še vse pare povezav med točkami v grafu. Dogovorimo se, da jih bomo skozi algoritem tudi pregledovali v naslednjem vrstnem redu: [A,B], [A,F], [B,D], [C,D], [C,E], [E,A], [E,F], [F,B], [F,D].

Dogovorimo se še, da bomo na slikah vozlišča, katerim vrednost se je spremenila, pobarvali z drugačno barvo kot so ostala vozlišča (s svetlo zeleno).

1. KORAK:

• Najprej preverimo povezavo [A,B]. Vzamemo vrednost v vozlišču A, ki je enaka neskončno. Če bomo tej vrednosti prišteli ceno med vozliščema A in B (to je 2) bo vrednost še vedno enaka neskončno, kar pa nikakor ni manj kot je trenutna vrednost vozlišča B (tudi ta je neskončno).
  Zato se tu ne bo zgodila nobena sprememba. Vozlišče B obdrži svojo trenutno vrednost.

• Podobno se bo zgodilo če pogledamo naslednji dve povezavi [A,F] in [B,D]. Če bomo trenutni vrednosti vozlišča A prišteli ceno med vozliščema A in F, ne bomo dobili manjše vrednosti kot je trenutna vrednost F-ja. Torej pri vozlišču F vrednosti ne spreminjamo.
  Podobno je tudi na povezavi med B in D, tako tudi D obdrži svojo staro vrednost.

• Prva sprememba se bo zgodila pri povezavi [C,D]. Vrednost pri vozlišču C je enaka 0. Prištejemo ji težo povezave med C in D ter dobimo: 0 + 3 = 3 < ∞ (kjer je ∞ vrednost v vozlišču D).
  Vidimo, da smo tako dobili vrednost povezave pri vozlišču D manjšo kot je bila na začetku, zato vozlišče D dobi novo vrednost: torej d[D] = 3. Poleg tega vozlišču D popravimo še prednika, ki bo sedaj vozlišče C: π[D] = C.
  Povezavo [C,D] bomo tako vključili v drevo najkrajših poti.
  

• Spodnja slika prikazuje graf po prvi spremembi. Z rdečo barvo bomo postopno gradili drevo najkrajših poti. Z zeleno barvo je pobarvano vozlišče, kateremu vrednost se je spremenila. Na sliki vidimo trenutno najkrajšo pot iz točke C do D (rdeča puščica), katere razdalja je enaka 3 enote.

Slika6: Stanje po prvi spremembi

• Naslednja je povezava [C,E]. Vzamemo vrednost v vozlišču C (ta je enaka 0) in mu prištejmo ceno povezave med C in E: 0 + 5 = 5 < ∞ (kjer je ∞ vrednost vozlišča E).
  Opazimo, da smo za vozlišče E s tem dobili manjšo vrednost kot je bila prejšnja, zato vozlišču vrednost popravimo: d[E] = 5. Poleg tega vozlišču določimo še novega prednika: π[E] = C.
  Povezavo [C,E] vključimo v drevo najkrajših poti.

• Za naslednjo povezavo vzamemo [E,A]. Trenutna vrednost vozlišča E je enaka 5, prištejmo ji ceno med vozliščema E in A: 5 - 3 = 2 < ∞ (kjer je ∞ trenutna vrednost vozlišča A).
  Ker smo tako pri vozlišču A dobili manjšo vrednost kot je bila prej, vozlišču določimo novo vrednost: d[A] = 2. Prav tako vozlišču spremenimo tudi prednika: π[A] = E.
  Povezavo [A,E] bomo dodali v drevo najkrajših poti.

Slika7: Stanje po zadnjih dveh spremembah

• Na zgornji sliki sta vozlišči, katerima vrednost se je nazadnje spremenila pobarvani z zeleno barvo. Z rdečimi puščicami je prikazano drevo najkrajših poti, kot smo ga zgradili do sedaj. In sicer vidimo, da je najkrajša razdalja od točke C do D vredna 3 enote, od C do E 5 enot in od C do A 2 enoti.

• Sedaj vzemimo povezavo [E,F]. Začetni vrednosti vozlišča E prištejemo ceno med E in F: 5 - 2 = 3 < ∞ (kjer je ∞ trenutna vrednost F).
  Vidimo, da je novo izračunana vrednost pri vozlišču D manjša kot je bila trenutna, zato D-ju popravimo vrednost: d[F]=2. Vozlišču F določimo še novega prednika: π[F] = E.
  Tudi to povezavo vključimo v drevo najkrajših poti.
  

• Naslednja je povezava [F,B]. Vrednosti vozlišča F prištejmo ceno povezave med F in B: 2 + 9 = 11 < ∞ (kjer je ∞ trenutna vrednost vozlišča B).
  Vidimo, da smo vozlišču B tako zmanjšali vrednost, zato mu vrednost spremenimo: d[B] = 11. Prav tako pa mu določimo novega prednika π[B] = F.
  Povezavo bomo vključili v drevo najkrajših poti.

• Ostala je še povezava [F,D]. Če vrednosti vozlišča F prištejemo ceno med F in D dobimo: 2 + 6 = 8 > 3 (kjer je 3 trenutna vrednost vozlišča D).
  Ker smo tako dobili vrednost v D večjo kot je trenutna vrednost vozlišča, vozlišču vrednosti ne spreminjamo.
• Ker smo sedaj že obiskali vsako povezavo iz grafa enkrat je prvi korak zaključen. Spodnja slika prikazuje stanje na grafu po zaključku prvega koraka. Z zeleno barvo sta pobarvani vozlišči, katerima vrednosti sta se nazadnje spremenili. Z rdečimi puščicami pa je označeno drevo najkrajših poti, kot smo ga zgradili do sedaj. Najkrajša pot od C do točke A je tako vredna 3 enote, od C do B 11 enot, od C do točke D 3 enote, od C do točke E 5 enot in od C do točke F 2 enoti.

Slika8: Stanje po prvem koraku

2. KORAK:

• Najprej vzamemo povezavo [A,B]. Vrednosti vozlišča A prištejemo ceno med A in B in dobimo: 2 + 2 = 4 < 11 (kjer je 11 trenutna vrednost vozlišča B).
  Vidimo da tako vozlišču B zmanjšamo vrednost, zato mu določimo novo vrednost: d[B] = 4.Popravimo mu še prednika π[A] = B.
  Povezavo [A,B] vključimo v drevo najkrajših poti, staro povezavo do vozlišča B pa iz drevesa odstranimo. Spodnja slika prikazuje stanje pred (leva) in po (desna) tej spremembi. Povezavo, ki je prečrtana iz drevesa najkrajših poti odstranimo. Na desni sliki je z zeleno barvo pobarvano vozlišče kateremu vrednost se je spremenila.
  Trenutne najkrajše razdalje so naslednje: od C do A je razdalja 2, od C do B je razdalja 4, od C do D je razdalja 3, od C do F je razdalja 2 in od C do E je razdalja 5.

Slika9: Stanje pred in po zadnji spremembi

• Naslednja je povezava [A,F]. Če vrednosti v vozlišču A prištejemo ceno med A in F, ne bomo v vozlišču F dobili manjše vrednosti kot je trenutna. Zato tu ni nobene spremembe.

• Sedaj pogedamo povezavo [B,D]. Vrednost v vozlišču B je enaka 4, ko ji prištejemo ceno povezave med vozliščema B in D dobimo vrednost 1, kar pa je manjše od 3, ki je trenutna vrednost vozlišča D.
  Vozlišču D tako določimo novo vrednost: d[D] = 1 in novega prednika: π[D] = B.
  Povezavo [B,D] tudi vključimo v drevo najkrajših poti, iz drevesa pa odstranimo povezavo [C,D], kjer je C predhodni prednik vozlišča D.

• Če sedaj pregledamo še vse povezave, ki jih še nismo pregledali v tem koraku opazimo, da nobenemu vozlišču več ne izboljšamo vrednosti. 2. korak je s tem zaključen.
  Stanje po zaključku 2. koraka prikazuje spodnja slika. Z zeleno barvo je pobarvano vozlišče, kateremu vrednost se je spremenila, z rdečimi puščicami pa je označeno drevo najkrajših poti. Vidimo, da je trenutna najkrjaša razdalja iz C v A vredna 2 enoti, iz C v B 4 enote, iz C v D 1 enoto, iz C v F 2 enoti ter iz C v E 5 enot.

Slika10: Stanje po zaključku 2. koraka

• Če preverimo sedaj vse povezave grafa vidimo, da ne bomo dobili več nobene spremembe, zato se je z 2. korakom algoritem zaključil. Tako slika 10 prikazuje tudi stanje po zalkjučku Bellman - Fordovega algoritma.

• Preverimo še, da v grafu ni nobenega negativnega cikla:

  • imamo en cikel A-C-E: vrednost 7 + 5 - 3= 9 > 0

• Poglejmo si še drevo najkrajših poti za dani graf:

Slika11: Drevo najkrajših poti za graf iz slike3

• Interpretacja rešitve:

  • najkrajša razdalja med C in E ima vrednost 5, do točke E pridemo iz C direktno
  • najkrajša razdalja med C in F ima vrednost 2, do točke F pridemo iz C preko točke E
  • najkrajša razdalja med C in A ima vrednost 2, do točke A pridemo iz C preko E
  • najkrajša razdalja med C in B ima vrednost 4, do točke B pridemo iz C preko E in A
  • najkrajša razdalja med C in D ima vrednost 1, do točke D pridemo iz C preko E, A in B

1. S pomočjo Bellman - Fordovega algoritma poiščemo najkrajše poti med vsemi pari točk v grafu.

2. Podan imamo spodnji graf. Recimo, da je A izhodiščno vozlišče. Katera od treh slik prikazuje drevo najkrajših poti, za dani graf?

3. Kakšne teže na povezavah dovoljuje Bellman - Fordov algoritem?

4. Na kakšnih grafih deluje Bellman - Fordov algoritem? (dve pravilni izbiri)

Preveri

• Boštjan Vilfan, Osnovni Algoritmi, Založba fakulteta za elektrotehniko in fakultete za računalništvo in informatiko, Ljubljana 2002
• Robin J. Wilson, John J. Watkins, Uvod v teorijo grafov, Društvo matematikov, fizikov in astronomov Slovenije, Ljubljana 1997
• Osnove algoritmov, Fakulteta za elektrotehniko, računalništvo in informatiko, Maribor 2009
• //www.fmf.uni-lj.si/~juvan/Racunalnistvo3/0708/gradivo/najkrajse_poti.pdf
• //wiki.fmf.uni-lj.si/wiki/Bellman-Fordov_algoritem
• //en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm