Algoritam Ford-Bellman-a
Stefan Đogo
Page 2
1. Biografija Ford-a i Bellman-a
Richard Bellma je rodjen 29 avgusta 1920 u Bruklinu, Njujork. Bio je američki
matematičar. Bellman je studirao matematiku na Bruklinskom koledžu (BA) i na
Univerzitetu u Vinskonsin. Radio je u oblasti teorijske fizike u Los Alamosu. Godine
1946 dobio je doktorat od Univerziteta Prinston. Nankon prijema doktorata ostaje na
Prinstonu kao docent a 1948 postaje i vanredni profesor na Univerzitetu u Stenfordu.
Godine 1952 pridruzuje se korporaciji RAND, gdje se fokusirao na donošenje odluka.
Njegov pronalazak dinamičnong programiranja 1953. je veliki napredak u ovoj oblasti, ali
i za mnoge druge oblasti kao sto je bioinformatika. 1965 godine postao je profesor
matematike. elektronike i medicine na Univerzitetu Južna Karolina.
Objavio je brojne knjige, članke i manografije. Po njemu su ime dobili brojni algoritmi
kao sto su Belmanov algorizam, kao i Ford.bellman-ov algoritam itd.
1966 godine održao je Međunarodnom kongresu matematičara u Moskvi (dinamičko
programiranje). 1970 godine gobio je prvu nagradu Norbert Viener i prvu nagradu u
Dikson nauke. Godine 1976 dobio je Džon fon Nojman theory nagradu.
Umro je 19. marta 1984 u Los Angeles-u.
Algoritam Ford-Bellman-a
Stefan Đogo
Page 4
algoritam 1957 godine zbog čega se algoritam ponekad naziva Ford-Belmanov_murov
algoritam.
Kako funkcioniše algoritam? Kao drugi problem dinamičkog programiranja , algoritam
izračunava najkraće puteve po buttom-up sistemu. Prvo izračunava najkraće rastojanje za
najkraće puteve koji imaju najviše jedan čvor prednosti na putu. Zatim izračunava
najkraće staze za dvije nost ivice, i tako dalje. posle te interacija spoljašnje petlje, najkraći
putevi sa najviše ivice se računaju. Ne može biti maksimalno |B| - 1 trake u svakom
jednostavnom putu, zbog čega se spoljna petlja radi |B| - 1 put. Ideja je, pod
prepostavkom da ne postoji negativna masa ciklusa, ako se izračuna najkraća putanja sa
najviše ivica, zatim interacija nad svim ivicama garancije dati najkraći put sa ( i+1) ivica.
Ivice sa negativnim težinama se mogu naći u mnogim primjenama grafova, što čini ovaj
algoritam veoma korisnim. Međutima ako algoritam sadrži " negativni cikl " na primjer
cikl čije ivice imaju negativan zbir , onda nema najjevtinijeg puta , ato sto u tom sličaju
svaki put može postati jevtiniji ako se još jednom prođe kroz negativni cikl . U takvim
slučajevima Ford-Bellman-ov algoritam može da otkrije negativne cikle i prijaviti njihovo
postojanje , ali ne može proizvesti tačan najkraći put ukoliko se do negativnog cikla maže
doći iz početnog čvora.
Ford-BEllman-ov algoritam radi bolje (bolje ne go Dijekstrin algoritam) za distribuirane
sisteme. za razliku od Dijekstre gdje treba pronaći minimalnu vrijednost svih čvorova, od
Ford-Bellman-ovog algoritma ivice se posmatraju jedna po jedna.
Razmotrimo sledeće primjere u grafu.
Neka izvor bude Vetek 0. Pokrene sve udaljenosti kao beskonačan, osim rastojanja do
samog izvora. Ukupan broj čvorova u grafu je 5 pa sve ivice moraju biti procesuirane 4
puta.
Neka sve ivice budu obradjene u sledećem redoslijedu: (B,E), (D,B). (B,D), (A,B), (A,C),
(D,C), (B,C), (E,D). Dobijamo sledeće distance kada sve ivice obrade prvi put. prvi red
pokazuje početnu razdaljinu, drugi rad pokazuje odstojanje prilikom ivice (B,E), (D,B),
(B,D), (A,B) se obrađuju. Treći red prikazuje odstojanje prilikom (A,C) se obrađuje.
Četvrti red prikazuje kada (D,C) , (B,C), (E,D) se obrađuju.
Algoritam Ford-Bellman-a
Stefan Đogo
Page 5
Prva interacija garantuje da se daju svi najkraći putevi koji su maksimalno jedna ivica
dugi. Dobijamo od sledećih distanci kada se sve ivce obrade po drugi put (poslednji red
prikazukje konačne vrijednosti).
Druga interacija garantuje da daju sve najkraće puteve koji su najviše dvije ivice dižine.
Algoritam obrađuje sve ivice još dva puta. Razdaljine su smanjili nakom druge interacije,
pa treća i četvrta interacija ne ažurira razdaljinu.
3
. O
algoritamu
Kao i Dijekstrin algoritam, i Ford Bellman-ov algoritam je osnovan na principu invertne
metode po imenu relaksacije, u kojem se aproksimacija tačne udaljenosti postepeno
smanjuje tačnijom vrijednosću sve dok se dok se ne dostigne optimalno rešenje. U oba
algoritma približna udaljenost do svakog čvora je uvjek je precjenjena vrijednost tačne
udaljenosti i zamjenjuje minimum svoje stare vrijednosti i dužine novootkrivenog puta.
Međutim Dijekstrin algoritam pohlepno bira čvor sa manjom težinom koji još uvjek nije
posećen i ponavlja isti postupak na svi ostalim ivicam ; u poređenju, Ford-Bellman-ovim
