Problem rutiranja u mrežama računara (ili distribuiranim sistemima) predstavlja odabir putanje kroz mrežu kojom paketi putuju od svoje početne destinacije do odredišta. Jedan od kriterijuma po kojima se vrši odabir putanje jeste taj da pređeni put bude što je moguće kraći. Kako bi se prenos podataka od jednog uređaja do drugog učinio što je moguće efikasnijim, potrebno je poznavati najkraći put između svaka dva uređaja. Ovaj problem moguće je modelovati u vidu grafa, tako što ćemo svaki od uređaja u mreži predstaviti čvorom grafa, a svaku od postojećih veza između uređaja granom grafa čija težina odgovara meri rastojanja između ta dva uređaja. Tada se polazni problem svodi na problem izračunavanja najkraćeg puta između svaka dva čvora u težinskom grafu.
Problem. Dat je težinski graf \(G=(V,E)\) (usmereni ili neusmereni). Odrediti puteve minimalne dužine između svaka dva čvora u grafu.
Ponovo, pošto govorimo o najkraćim putevima, težine grana možemo interpretirati kao dužine grana. Ovaj problem nazivamo problem nalaženja svih najkraćih puteva (engl. all pairs shortest path). Za početak ćemo se zadovoljiti nalaženjem dužina svih najkraćih puteva, umesto samih najkraćih puteva. Pretpostavimo da je graf usmeren; sve što će biti rečeno važi i za neusmerene grafove. Težine grana u grafu mogu biti negativne, ali u grafu ne sme postojati ciklus negativne težine.
Jedan mogući pristup je da se Belman-Fordov algoritam (ili Dajkstrin algoritam, ako su težine grana nenegativne) pokrene iz svakog čvora grafa. Međutim, videćemo da postoje i efikasniji algoritmi koji direktno rešavaju ovaj problem.
Kao i obično, pokušajmo sa direktnim induktivno-rekurzivnim pristupom. Može se koristiti indukcija po broju grana ili po broju čvorova u grafu. Označimo sa \(d(u,v)\) dužinu grane \((u,v)\), a sa \(\overline{\mathit{SP}}(u, v)\) dužinu trenutno poznatog najkraćeg puta od čvora \(u\) do čvora \(v\).
2.11.1 Algoritam zasnovan na indukciji po broju grana u grafu
Razmotrimo najpre indukciju po broju grana. Pretpostavimo da smo iz grafa \(G\) uklonili granu \((u,v)\) i da smo rešili problem na preostalom grafu \(G'\), tj. da znamo dužine najkraćih puteva između svaka dva čvora u grafu \(G'\). Kako se menjaju najkraći putevi u grafu nakon dodavanja grane \((u,v)\) u graf? Nova grana može pre svega da predstavlja kraći put od do sada pronađenog najkraćeg puta od čvora \(u\) do čvora \(v\). Dakle, potrebno je proveriti da li važi \(d(u,v)<\overline{\mathit{SP}}(u, v)\) i ako važi, postaviti vrednost \(\overline{\mathit{SP}}(u, v)\) na \(d(u,v)\). Pored toga, dodavanjem grane \((u,v)\) može se promeniti i najkraći put između proizvoljna druga dva čvora \(s\) i \(t\). Da bi se ustanovilo ima li promene, treba sa prethodno poznatom najmanjom dužinom puta od čvora \(s\) do čvora \(t\) uporediti zbir dužina najkraćeg puta od \(s\) do \(u\), dužine grane \((u,v)\) i dužine najkraćeg puta od \(v\) do \(t\). Dakle, ako je \(\overline{\mathit{SP}}(s, u)+d(u,v)+\overline{\mathit{SP}}(v, t) < \overline{\mathit{SP}}(s, t)\) potrebno je novu vrednost \(\overline{\mathit{SP}}(s, t)\) postaviti na \(\overline{\mathit{SP}}(s, u)+d(u,v)+\overline{\mathit{SP}}(v, t)\).
Pošto je broj parova čvorova \(O(|V|^2)\), pri dodavanju grane \((u,v)\) potrebno je izvršiti \(O(|V|^2)\) provera. Ovaj postupak je potrebno sprovesti za svaku granu grafa, te je složenost algoritma za nalaženje svih najkraćih puteva zasnovanog na indukciji po broju grana u najgorem slučaju \(O(|E|\cdot |V|^2)\). Pošto je broj grana najviše \(O(|V|^2)\), složenost ovog algoritma iznosi \(O(|V|^4)\). Ovo je veoma neefikasno, pa ovaj algoritam nećemo implementirati.
2.11.2 Algoritam zasnovan na indukciji po broju čvorova u grafu
Razmotrimo sada indukciju po broju čvorova. Pretpostavimo da smo iz grafa \(G\) uklonili čvor \(u\) i da smo između svaka druga dva čvora u grafu pronašli najkraći put. Kako se menjaju najkraći putevi u grafu ako se u graf doda novi čvor \(u\)? Potrebno je najpre pronaći najkraće puteve od čvora \(u\) do svih ostalih čvorova, i najkraće puteve od svih ostalih čvorova do čvora \(u\). Pošto su dužine najkraćih puteva koji ne sadrže \(u\) već poznate, određivanje najkraćeg puta od čvora \(u\) do proizvoljnog čvora \(w\) svodi se na određivanje samo prve grane na tom putu; ako je to grana \((u,v)\), onda je dužina najkraćeg puta od čvora \(u\) do čvora \(w\) jednaka zbiru dužine grane \((u,v)\) i dužine najkraćeg puta od \(v\) do \(w\), koji je već poznat. Potrebno je, dakle, da uporedimo ove zbirove za sve grane koje polaze iz čvora \(u\), i da među njima izaberemo najmanji:
Najkraći put od proizvoljnog čvora \(w\) do čvora \(u\) može se pronaći na sličan način. Ove provere su u najgorem slučaju (kada iz čvora \(u\) polazi/u njega dolazi \(\Theta(|V|)\) grana) složenosti \(O(|V|^2)\).
Međutim, dodavanje čvora \(u\) može skratiti puteve između neka druga dva čvora, jer put preko \(u\) može biti kraći nego putevi koji ne prolaze kroz \(u\). Zato je, dodatno, potrebno za svaki par čvorova proveriti da li između njih postoji novi kraći put kroz novi čvor \(u\). Za proizvoljna dva čvora \(s\) i \(t\) grafa, da bi se ustanovilo postoji li kraći put preko čvora \(u\), potrebno je sa prethodno poznatom najmanjom dužinom puta od \(s\) do \(t\) uporediti zbir dužine najkraćeg puta od \(s\) do \(u\) i dužine najkraćeg puta od \(u\) do \(t\). Ako važi \(\overline{\mathit{SP}}(s, u)+\overline{\mathit{SP}}(u, t) < \overline{\mathit{SP}}(s, t)\), ažuriramo vrednost \(\overline{\mathit{SP}}(s, t)\).
Ovo uključuje ukupno \(O(|V|^2)\) provera i sabiranja posle dodavanja svakog novog čvora, pa je složenost ovakvog algoritma u najgorem slučaju \(O(|V|\cdot|V|^2)=O(|V|^3)\). Ukupan broj koraka za određivanje dužina najkraćih puteva od i do novododatog čvora je takođe \(O(|V|^3)\). Dakle, ispostavlja se da je za rešavanje ovog problema efikasnija indukcija po broju čvorova nego indukcija po broju grana.
Razmotrimo implementaciju algoritma za računanje svih najkraćih puteva u grafu zasnovanog na indukciji po čvorovima, u slučaju kada je graf zadat matricom povezanosti. Naime, ovde nam je ta reprezentacija pogodnija od listi povezanosti jer dužine grana odgovaraju inicijalnim najkraćim rastojanjima između čvorova.
constint INF = numeric_limits<int>::max();// odredjujemo sve najkrace puteve indukcijom po broju cvorovavector<vector<int>> sviNajkraciPutevi(const vector<vector<int>>& matricaPovezanosti) {int brojCvorova = matricaPovezanosti.size(); vector<vector<int>> najkraciPut(brojCvorova);for (int i = 0; i < brojCvorova; i++) najkraciPut[i].resize(brojCvorova, INF);// dodajemo jedan po jedan cvorfor (int i = 0; i < brojCvorova; i++) { najkraciPut[i][i] = 0;// odredjujemo najkrace puteve od cvora i do svih prethodnih// cvorova jfor (int j = 0; j < i; j++) {// pretpostavljamo da je direktno rastojanje najkrace najkraciPut[i][j] = matricaPovezanosti[i][j];// proveravamo da li je mozda bolji put od i do j koji vodi preko// nekog prethodnog cvora kfor (int k = 0; k < i; k++)// ako postoji grana od i do k i put od k do jif (matricaPovezanosti[i][k] != INF && najkraciPut[k][j] != INF && matricaPovezanosti[i][k] + najkraciPut[k][j] < najkraciPut[i][j]) najkraciPut[i][j] = matricaPovezanosti[i][k] + najkraciPut[k][j]; }// odredjujemo najkrace puteve do cvora i od svih prethodnih// cvorova jfor (int j = 0; j < i; j++) {// pretpostavljamo da je direktno rastojanje najkrace najkraciPut[j][i] = matricaPovezanosti[j][i];// proveravamo da li je mozda bolji put od cvora j do i koji// vodi preko nekog prethodnog cvora kfor (int k = 0; k < i; k++)// ako postoji grana od i do k i put od k do jif (najkraciPut[j][k] != INF && matricaPovezanosti[k][i] != INF && najkraciPut[j][k] + matricaPovezanosti[k][i] < najkraciPut[j][i]) najkraciPut[j][i] = najkraciPut[j][k] + matricaPovezanosti[k][i]; }// ažuriramo rastojanja od prethodnih cvorova j do prethodnih// cvorova k, analizirajuci puteve koji vode preko cvora ifor (int j = 0; j < i; j++)// ako postoji put od j do i i ako postoji put od i do kfor (int k = 0; k < i; k++)if (najkraciPut[j][i] != INF && najkraciPut[i][k] != INF && najkraciPut[j][i] + najkraciPut[i][k] < najkraciPut[j][k]) najkraciPut[j][k] = najkraciPut[j][i] + najkraciPut[i][k]; }return najkraciPut;}int main() {// broj cvorova u grafuint n; cin >> n;// matrica susedstva grafa koji sadrzi n cvorova vector<vector<int>> M(n);for (int i = 0; i < n; i++) { M[i].resize(n);for (int j = 0; j < n; j++) { cin >> M[i][j];// ako je uneto -1, tezinu grane postavljamo na +beskonacno// pretpostavljamo da u grafu ne postoji grana negativne tezineif (M[i][j] == -1) M[i][j] = INF; } }// racunamo najkrace puteveauto duzinaPuta = sviNajkraciPutevi(M);// stampamo najkrace putevefor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)if (duzinaPuta[i][j] != INF) cout << duzinaPuta[i][j] << "\t";else cout << "-\t"; cout << endl; } cout << endl;return0;}
2.11.3 Flojd-Varšalov algoritam
Pokazuje se da postoji još jednostavnija induktivna konstrukcija za rešavanje ovog problema. Ideja na kojoj se zasniva ovaj algoritam je da se ne menja broj čvorova ili grana u grafu, već da se uvedu ograničenja na tip dozvoljenih puteva. Naime, razmatraju se samo putevi koji kao međučvorove koriste čvorove iz zadatog skupa čvorova, pri čemu se u svakom koraku taj skup proširuje jednim novim čvorom. Na početku je taj skup prazan, pa u obzir dolaze samo grane grafa, a na kraju obuhvata sve čvorove grafa, pa u obzir dolaze svi mogući putevi. Numerišimo čvorove grafa na proizvoljan način brojevima od \(1\) do \(|V|\). Put od čvora \(u\) do čvora \(v\) zove se \(k\)-put, gde je \(k\in\{0,1,\ldots,|V|\}\), ako su redni brojevi svih čvorova na tom putu (izuzev \(u\) i \(v\)) manji ili jednaki \(k\) (skup dopuštenih međučvorova je, dakle, skup čvorova označen brojevima od 1 do \(k\)). Specijalno, \(0\)-put od čvora \(u\) do čvora \(v\) može biti samo direktna grana od čvora \(u\) do čvora \(v\) (pošto se nijedan drugi čvor ne može pojaviti na tom putu).
Primer 2.11.1. Razmotrimo primer grafa sa slike 1. Neka su redni brojevi čvorova \(a\), \(d\), \(c\), \(b\) redom \(1\), \(2\), \(3\), \(4\). Put \((a,b)\) od čvora \(a\) do čvora \(b\) dužine \(10\) je \(0\)-put, jer se sastoji od samo jedne grane (nema usputnih čvorova na putu). Put \((a, d, c, b)\) dužine \(6\) je \(3\)-put, jer su redni brojevi svih čvorova na tom putu manji ili jednaki \(3\) (istovremeno je i \(4\)-put), ali nije npr. \(2\)-put. Slično, put \((c,a,b)\) je \(1\)-put, jer su redni brojevi svih čvorova (u ovom slučaju jednog jedinog čvora) na putu manji ili jednaki \(1\) (ovaj put je, takođe, i \(2\)-put, \(3\)-put i \(4\)-put). Primetimo da je najkraći \(0\)-put (istovremeno i najkraći \(1\)-put i najkraći \(2\)-put) od čvora \(a\) do čvora \(b\) put \((a,b)\) dužine \(10\), dok je najkraći \(3\)-put (i istovremeno najkraći \(4\)-put) \((a,d,c,b)\) dužine \(6\).
Slika 1: Ilustracija \(k\)-puteva u usmerenom težinskom grafu.
Razmotrimo algoritam zasnovan na indukciji po opadajućem broju ograničenja na tip dozvoljenih puteva.
Induktivna hipoteza. Umemo da odredimo dužine najkraćih \((k-1)\)-puteva između svaka dva čvora.
Baza indukcije je slučaj \(k=1\), kad se razmatraju samo direktne grane i rešenje je očigledno: najkraći \(0\)-put između dva čvora jednak je dužini grane ako ona postoji, a \(+\infty\) ako grana ne postoji.
Pretpostavimo da je induktivna hipoteza tačna i da hoćemo da je proširimo na \(k\)-puteve. Potrebno je da odredimo najkraće \(k\)-puteve između svaka dva čvora. Neka je \(v_k\) čvor sa rednim brojem \(k\). Proizvoljan najkraći \(k\)-put sadrži čvor \(v_k\) najviše jednom. Naime, pretpostavka je da u grafu ne postoji ciklus negativne dužine, pa najkraći put ne može dva puta da prođe kroz čvor \(v_k\) — u protivnom bi se put mogao skratiti izbacivanjem ciklusa od grana između prvog i drugog pojavljivanja čvora \(v_k\). Najkraći \(k\)-put od čvora \(s\) do čvora \(t\) je ili najkraći \((k-1)\)-put od čvora \(s\) do čvora \(t\) ili se sastoji od najkraćeg \((k-1)\)-puta od čvora \(s\) do čvora \(v_k\), i najkraćeg \((k-1)\)-puta od čvora \(v_k\) do čvora \(t\) jer su čvorovi na \(k\)-putu od \(s\) do \(v_k\) i od \(v_k\) do \(t\) numerisani brojevima manjim ili jednakim \(k-1\) (slika 2). Prema induktivnoj hipotezi mi već znamo dužine najkraćih \((k-1)\)-puteva. Dakle, da bismo pronašli dužinu najkraćeg \(k\)-puta od čvora \(s\) do čvora \(t\) dovoljno je da saberemo ove dve dužine i zbir uporedimo sa dužinom najkraćeg \((k-1)\)-puta od čvora \(s\) do čvora \(t\).
Slika 2: Ilustracija procesa računanja najkraćih \(k\)-puteva: najkraći \((k-1)\)-put od čvora \(s\) do čvora \(t\) poredimo sa zbirom najkraćih \((k-1)\)-puteva od \(s\) do \(v_m\) i od \(v_m\) do \(t\).
Do ovog algoritma su nezavisno došli i objavili ga Robert Flojd i Stiven Varšal i poznat je pod nazivom Flojd-Varšalov algoritam. Napomenimo da je nekoliko godina pre njih do istog algoritma došao i Bernard Roj, međutim, taj rezultat je prošao nezapaženo. Ipak, negde u literaturi se ovaj algoritam pominje i pod nazivom Roj-Varšalov ili Roj-Flojdov algoritam. Flojd-Varšalov algoritam je za konstantan faktor brži od algoritma zasnovanog na primeni indukcije po broju čvorova i lakše ga je realizovati.
Prethodnim induktivnim razmatranjem dokazali smo korektnost ovog algoritma.
Teorema 2.11.1.[Korektnost Flojd Varšalovog algoritma] Za dati usmeren težinski graf \(G = (V, E)\) bez ciklusa negativne težine, Flojd-Varšalov algoritam ispravno izračunava najkraća rastojanja između svih parova čvorova.
Do sad smo se bavili izračunavanjem dužina najkraćih puteva između svaka dva čvora u grafu. Razmotrimo sada kako bismo mogli da rekonstruišemo same najkraće puteve, a da pritom čuvamo što manje informacija: poželjno je da za svaki najkraći put čuvamo samo po jednu vrednost. Prisetimo se da je u prethodnim algoritmima za svaki čvor bilo dovoljno čuvati pretposlednji čvor na najkraćem putu do tog čvora, jer je svaki naredni najkraći put bio dobijen produživanjem nekog prethodno određenog najkraćeg puta jednom novom granom. Ovde takva rekonstrukcija ne bi imala smisla, jer se najkraći putevi konstruišu na drugačiji način, pa algoritam rekonstrukcije najkraćih puteva mora da prati postupak konstrukcije najkraćih puteva. U algoritmu se tekući najkraći put između dva čvora menja onda kada je put kroz novorazmatrani čvor \(v_k\) kraći nego prehodno određeni najkraći \((k-1)\)-put. Dakle, možemo angažovati dodatnu matricu \(put\) u kojoj ćemo na poziciji \((i,j)\) pamtiti maksimalnu vrednost \(k\) takvu da čvor \(v_k\) pripada najkraćem putu od čvora \(i\) do čvora \(j\), a ako je najkraći put direktna grana od \(i\) do \(j\), onda vrednost \(put[i][j]\) možemo postaviti na \(i\). Ako se prilikom traženja najkraćeg puta od čvora \(i\) do čvora \(j\) nađe kraći put koji vodi preko čvora \(v_k\), ažuriraćemo vrednost \(put[i][j]\) na \(k\). Ispisivanje najkraćeg puta od čvora \(i\) do čvora \(j\) se onda svodi na ispisivanje najkraćeg puta od čvora \(i\) do čvora sa rednim brojem \(put[i][j]\) za kojim sledi najkraći put od čvora sa rednim brojem \(put[i][j]\) do čvora \(j\).
U algoritmu koji sledi pretpostavićemo da u grafu ne postoji grana negativne težine. Pretpostavljamo da je graf zadat matricom povezanosti jer ona gotovo u potpunosti kodira dužine \(0\)-puteva u grafu. Naime, da bismo dobili dužine \(0\)-puteva jedino je potrebno u poljima matrice koja odgovaraju parovima čvorova između kojih ne postoji grana postaviti umesto vrednosti \(-1\) vrednost \(+\infty\). Kao numeraciju čvorova iskoristićemo njihov indeks.
constint INF = numeric_limits<int>::max();// funkcija koja stampa najkraci put od cvora i do cvora j// bez ispisivanja cvora jvoid odstampajPut(const vector<vector<int>>& put, int i, int j) {if (put[i][j] == -1)return;// put od i do j odgovara direktnoj grani (i,j)if (put[i][j] == i) cout << i << " - ";else{// stampamo put od cvora i do cvora k, gde je k maksimalni redni broj cvora// koji pripada tom putu, pa zatim put od cvora k do cvora j odstampajPut(put, i, put[i][j]); odstampajPut(put, put[i][j], j); }}// funkcija koja stampa najkrace puteve izmedju svaka dva cvora u grafuvoid odstampajPuteve(const vector<vector<int>>& duzinaPuta,const vector<vector<int>>& put, int brojCvorova) { cout << "Matrica najkracih rastojanja jednaka je: " << endl;for (int i = 0; i < brojCvorova; i++) {for (int j = 0; j < brojCvorova; j++)if (duzinaPuta[i][j] != INF) cout << duzinaPuta[i][j] << "\t";else cout << "-\t"; cout << endl; } cout << endl;for (int i = 0; i < brojCvorova; i++)for (int j = 0; j < brojCvorova; j++)if (i != j && put[i][j] != -1) { cout << "Najkraci put od cvora " << i << " do cvora " << j << " je: "; odstampajPut(put,i,j); cout << j << endl; }}// funkcija koja racuna najkrace puteve izmedju svaka dva cvoravoid sviNajkraciPutevi(const vector<vector<int>> &matricaPovezanosti) {int brojCvorova = matricaPovezanosti.size();// inicijalizujemo matricu koja cuva duzine najkracih puteva// na duzine direktnih grana, a ako direktna grana ne postoji// na vrednost +beskonacno vector<vector<int>> najkraciPut = matricaPovezanosti; vector<vector<int>> put(brojCvorova); // inicijalizujemo drugu matricu pomocu koje cemo// rekonstruisati najkrace putevefor (int i = 0; i < brojCvorova; i++) { put[i].resize(brojCvorova);for (int j = 0; j < brojCvorova; j++)// ako postoji direktna grana od cvora i do cvora j// pamtimo tu informacijuif (matricaPovezanosti[i][j] != INF) put[i][j] = i;// inace za i<>j postavljamo da je maksimalna oznaka cvora// na trenutnom putu -1 elseif (i != j) put[i][j] = -1;// slucaj kada razmatramo put od cvora do njega samogelse put[i][j] = 0; }// proveravamo da li k-putevi skracuju puteve izmedju cvora i i jfor (int k = 0; k < brojCvorova; k++)for (int i = 0; i < brojCvorova; i++)for (int j = 0; j < brojCvorova; j++)// ako postoji neki put od i do k i ako postoji neki put od k do jif (najkraciPut[i][k] != INF && najkraciPut[k][j] != INF && najkraciPut[i][k] + najkraciPut[k][j] < najkraciPut[i][j]) { najkraciPut[i][j] = najkraciPut[i][k] + najkraciPut[k][j];// postavljamo da je na putu od cvora i do cvora j// maksimalna oznaka cvora jednaka k put[i][j] = k; }// proveravamo da li je u grafu postojao ciklus negativne duzinebool negativniCiklus = false;for (i = 0; i < brojCvorova; i++)if (najkraciPut[i][i] < 0) { cout << "U grafu postoji ciklus negativne duzine" << endl; negativniCiklus = true;break; }// ako ne postoji ciklus negativne duzine// stampamo sve najkrace puteveif (!negativniCiklus) odstampajPuteve(najkraciPut, put, brojCvorova);}int main() {// broj cvorova u grafuint n; cin >> n;// matrica susedstva grafa koji sadrzi n cvorova vector<vector<int>> M(n);// ucitavamo matricu susedstva tezinskog grafafor (int i = 0; i < n; i++) { M[i].resize(n);for (int j = 0; j < n; j++) { cin >> M[i][j];// ako je uneto -1, tezinu grane postavljamo na +beskonacno// pretpostavljamo da u grafu ne postoji grana negativne tezineif (M[i][j] == -1) M[i][j] = INF; } }// racunamo najkrace puteve izmedju svaka dva cvora sviNajkraciPutevi(M);return0;}
Napomenimo da je u trostruko ugnežđenoj petlji neophodno da spoljašnja petlja kontroliše parametar \(k\) koji ograničava tip dozvoljenih puteva, dok se unutrašnje dve petlje koriste se za proveru svih parova čvorova. Zapaža se da se ova provera može izvršavati sa parovima čvorova u proizvoljnom redosledu, jer je svaka od provera potpuno nezavisna od ostalih.
Primer 2.11.2. Razmotrimo primer grafa sa slike 3 kod koga su težine svih grana jednake \(1\). Neka su redni brojevi čvorova \(0\), \(1\), \(2\) i \(3\) sa slike redom jednaki \(1\), \(2\), \(3\) i \(4\). U njemu postoji put od čvora \(0\) do čvora \(1\) dužine \(3\) i on predstavlja najkraći put od čvora \(0\) do čvora \(1\). Razmotrimo varijantu Flojd-Varšalovog algoritma sa narednim, malo izmenjenim redosledom petlji:
for (int i = 0; i < brojCvorova; i++)for (int j = 0; j < brojCvorova; j++)for (int k = 0; k < brojCvorova; k++)if (najkraciPut[i][k] != INF && najkraciPut[k][j] != INF && najkraciPut[i][k] + najkraciPut[k][j] < najkraciPut[i][j]) { najkraciPut[i][j] = najkraciPut[i][k] + najkraciPut[k][j];
pri čemu promenljiva \(k\) kontroliše tip dozvoljenih puteva, \(i\) polazni čvor, a \(j\) krajnji čvor puta. Ovaj algoritam odgovara tome da se za svaka dva fiksirana čvora numerisana vrednostima \(i\) i \(j\) prolazi kroz sve čvorove \(k\) i razmatra da li postoji put preko čvora \(k\). Za vrednost promenljivih \(i=0\) i \(j=1\) proveravaju se redom vrednosti \(0,1,2\) i \(3\) za \(k\) i pošto ne postoji \(k\) tako da istovremeno postoji i grana \((i,k)\) i grana \((k,j)\), put od čvora \(0\) do čvora \(1\) ne bi bio pronađen, iako on postoji u grafu. Naime, da bismo otkrili najkraći put (tj. najkraći \(4\)-put) od čvora \(0\) do čvora \(1\) potrebno je prethodno odrediti najkraći \(3\)-put od čvora \(0\) do čvora \(1\), što u ovoj varijanti algoritma nije slučaj. Zaključujemo da ovakav redosled petlji ne omogućava nalaženje svih najkraćih puteva. Dakle, važno je da spoljašnja od tri petlje prolazi skupom vrednosti \(k\), gde \(k\) kontroliše tip dozvoljnog puta.
Slika 3: Usmereni težinski graf za koji modifikacija Flojd-Varšalovog algoritma kod koje unutrašnja petlja kontroliše tip dozvoljenih puteva ne vraća najkraći put od čvora \(0\) do čvora \(1\).
Primetimo da Flojd-Varšalov algoritam radi korektno i za grafove koji imaju negativne težine grana (sve dok u grafu ne postoji ciklus negativne težine) jer korektnost algoritma ne zavisi od toga da su težine grana u grafu nenegativne.
Ukoliko polazni graf ima ciklus negativne težine, to se može utvrditi tako što će nakon izvršavanja Flojd-Varšalovog algoritma dužina najkraćeg puta od nekog čvora do njega samog biti manja od 0, odnosno neka vrednost na dijagonali matrice najkraciPut je manja od 0. Naime, inicijalno važi najkraciPut[i][i] = 0 za svako \(i\). Flojd-Varšalov algoritam računa najkraće puteve između svaka dva čvora u grafu, pa i između parova istih čvorova. Ako čvor \(i\) pripada ciklusu negativne težine, onda će Flojd-Varšalov algoritam razmotriti i put od čvora \(i\) do njega samog kroz grane ovog ciklusa i inicijalnu vrednost \(0\) smanjiti na težinu ovog ciklusa.
Ako se u nekom koraku spoljašnje petlje ustanovi da se matrica najkraciPut nije promenila, algoritam se može ranije prekinuti.
Za svaku vrednost \(k\) algoritam izvršava jedno sabiranje i jedno upoređivanje za svaki par čvorova. Broj koraka indukcije je \(|V|\), pa je ukupan broj sabiranja, odnosno upoređivanja, najviše \(|V|^3\). Prisetimo se da je vremenska složenost Dajkstrinog algoritma za nalaženje najkraćih puteva od jednog zadatog čvora u grafu koji ne sadrži grane negativne dužine \(O((|V|+|E|)\log|V|)\). Ako je graf gust, pa je broj grana \(\Theta(\vert V\vert ^2)\), onda je za određivanje svih najkraćih puteva u grafu Flojd-Varšalov algoritam efikasniji od izvršavanja Dajkstrinog algoritma od svakog polaznog čvora u grafu. S druge strane, ako graf nije gust (pa ima, na primer, \(O(\vert V\vert)\) grana), onda je bolja vremenska složenost \(O(|V|(|V|+|E|)\log |V|)\) koja potiče od \(|V|\) puta upotrebljenog algoritma za najkraće puteve od jednog čvora. Jedna od prednosti Flojd-Varšalovog algoritma je, svakako, i njegova jednostavna realizacija, kao i to što je primenljiv i na grafove koji imaju negativne grane.
Primer 2.11.3. Razmotrimo postupak određivanja najkraćih puteva između svaka dva čvora u grafu sa slike 4.
Slika 4: Usmereni težinski graf za koji tražimo najkraći put između svaka dva čvora.
Iz poslednje matrice najkraciPut možemo pročitati da je najkraći put od čvora \(1\) do čvora \(3\) dužine \(4\), a iz matrice put da je maksimalni indeks čvora na tom najkraćem putu jednak \(4\). Dakle, da bismo rekonstruisali najkraći put, potrebno je da na najkraći put od čvora \(1\) do čvora \(4\) nadovežemo najkraći put od čvora \(4\) do čvora \(3\). Iz matrice put možemo pročitati da je najveći indeks čvora na najkraćem putu od čvora \(1\) do čvora \(4\) baš jednak \(1\), što nam govori da je taj put direktna grana između tih čvorova. Iz matrice put možemo takođe pročitati da je najveći indeks čvora na najkraćem putu od čvora \(4\) do čvora \(3\) jednak \(2\), što nam govori da taj put određujemo tako što na najkraći put od čvora \(4\) do čvora \(2\) nadovežemo najkraći put od čvora \(2\) do čvora \(3\). Iz matrice put možemo zaključiti da oba ova puta odgovaraju direktnim granama. Konačno, zaključujemo da je najkraći put od čvora \(1\) do čvora \(3\) jednak \((1,4,2,3)\).
U narednom apletu možete videti kako funkcioniše Flojd-Varšalov algoritam.
