Poiskati dolžine najkrajših poti od izhodiščnega vozlišča do vseh ostalih vozlišč () in njihove optimalne predhodnike v omrežju (grafu ) utežno usmerjenih povezav.

Eden izmed načinov, da rešimo naš problem je Bellman-Ford-ov algoritem.

Uteženo usmerjeni graf je urejen par , kjer so:

- uteži ... števila, ki pomenijo vrednost (stroške, cene) povezav v grafu ;

- ... neprazna končna množica vozlišč v grafu ... ,
pri čemer je -to vozlišče v grafu ,
j = 1,2, ...,n;

- ... množica uteženih povezav v grafu ... ,
pri čemer je (začetek povezave, konec povezave, utež povezave),
i = 1,2, ...,m.

Predpostavka:
- ne dovoljujemo negativnih ciklov.

Dano imamo optimalno pot iz v : -> -> -> -> .
Velja:
je optimalni predhodnik vozlišča ,
je optimalni predhodnik vozlišča ,
je optimalni predhodnik vozlišča in
je optimalni predhodnik vozlišča .

VHODNI PODATKI:
- … množica uteženih povezav,
- … neprazna končna množica vozlišč,
- … izhodiščno vozlišče.

IZHODNI PODATKI:
- … dolžine najkrajših poti od izhodiščnega vozlišča do vozlišč ,
- … optimalni predhodniki (očetje) vozlišč .
j = 1,2, ...,n;

PROGRAM V JAVI:
prenesi

Da pridemo do optimalne rešitve preko BF algoritma moramo največ -krat skozi vse povezave, če vemo, da je število vozlišč v grafu enako .

Če v omrežju ni negativnih ciklov, najkrajša pot lahko obišče vsako vozlišče največ enkrat. Če ima graf manj povezav, je treba pregledati manj možnosti. Najslabše je v polnem grafu (vsebuje vse možne povezave), kjer ima vsako vozlišče sosedov.

Glavna prednost BF v primerjavi z večino ostalimi algoritmi je ravno v tem, da nam poišče dolžine najkrajših poti od izhodiščnega vozlišča do VSEH ostalih vozlišč in njihove optimalne predhodnike. V večini nam algoritmi za iskanje najkrajših poti poiščejo SAMO ENO najkrajšo pot (recimo od do ).

- OMREŽJE CESTNIH POVEZAV:
Iščemo najkrajšo pot iz Ljubljane v Maribor.
Ljubljana - Kranj - Velenje - Maribor,
Ljubljana - Trbovlje - Celje - Maribor,
Ljubljana - Celje - Maribor,
Ljubljana - Trbovlje - Celje - Ptuj - Maribor,
... Hkrati bi lahko tudi poiskali najkrajšo pot iz Ljubljane v Kranj, itd.

- OMREŽJE ELEKTRIČNE NAPELJAVE:
Polagamo električno napeljavo v Kočevju iz Tomšičeve ulice v Streliško ulico s čim manjšimi stroški.
Tomšičeva ulica - Tesarska ulica - Podgorska ulica - Streliška ulica,
Tomšičeva ulica - Ljubljanska ulica - Podgorska ulica - Streliška ulica,
Tomšičeva ulica - Turjaška ulica - Streliška ulica,
... Hkrati bi lahko tudi poiskali opt. iz Tomšičeve v Podgorsko, itd.

- OMREŽJE HIDROVODNE NAPELJAVE:
.
.
.

Dano je omrežje:

omrežje1

Poiščimo dolžine vseh najkrajših poti (optimalne vrednosti) iz vozlišča do vozlišč (in vmesna vozlišča) preko Bellman-Ford algoritma.

REŠITEV V OBLIKI FILMČKA

Dano je (malo večje) omrežje:

Poiščimo dolžine vseh najkrajših poti iz vozlišča do vseh ostalih vozlišč in njihove optimalne predhodnike (očete) preko BF.

RAČUNAMO PO KORAKIH :

korak


.
.
.
(REŠITEV:)
korak

Dano je omrežje:





Poiščimo dolžine vseh najkrajših poti iz vozlišča do vozlišč preko BF.

Dano je omrežje:





Poiščimo dolžine vseh najkrajših poti iz vozlišča do vozlišč preko BF.

Dano je omrežje:





Poiščimo dolžine vseh najkrajših poti iz vozlišča do vozlišč preko BF.

(Graf vsebuje negativni cikel!)

Računamo po korakih:

ko gremo PRVIČ skozi vse povezave:



ko gremo DRUGIČ skozi vse povezave:



ko gremo TRETJIČ skozi vse povezave:



Opazimo: in da je iz koraka v korak boljši.

Torej iz koraka v korak dobivamo boljšo rešitev in predhodniki se ne spreminjajo (večkrat ko prehodimo eno in isto pot (cikel) boljši je optimum).
Ugotovimo, da je problem iskanja najkrajših poti nesmiseln, če imamo opravka z negativnimi cikli.

Bellman_Ford_1

Bellman_Ford_2