Algoritmul Floyd-Warshall

Din laboratorul anterior am vazut ca intr-un graf orientat sau neorientat pot aparea costuri pe arce, care pot avea valori positive sau negative. De asemenea am vazut ca pentru a gasi drumul intre doua noduri putem folosi algoritmul lui Dijstra, care merge doar pe arce cu costuri positive, sau algoritmul Bellman-Ford, care merge sip e arce cu costuri negative. Dar pentru un graf cu multe arce, algoritmul este foarte incet si atunci solutia este daca folosim Floyd-Warshall.

Algoritmul foloseste concepte din programarea dinamica pentru a descoperii cel scurt drum intre doua noduri. Dupa cum am spus, algoritmul merge sip e arce negative, dar nu si pe "cicluri negative".

Algoritmul compara toate drumurile posibile din graf dintre fiecare 2 noduri. Un lucru foarte bun este ca reuseste aceasta operatie in doar V3 comparari, incrementand o imbunatatire constanta a unei estimari a celei mai scurte cai dintre doua noduri, pana cand estimarea este cunoscuta ca fiind cea optima. Considerand un graf G=(V,E), fiecare varf numerotat de la 1 la N. Consideram functia, shortestPath(i,j,k) care returneaza cea mai scurta cale (drum) de la i la j folosind doar varfurile de la 1 la k ca puncte intermediare de-a lungul caii. Acum, avand aceasta functie, ne intereseaza sa gasim cea mai scurta cale de la fiecare i la fiecare j folosind doar nodurile de la 1 la k+1. Sunt doua drumuri posibil candidate: fie calea "buna" (scurta) foloseste doar setul de noduri (1 k); sau exista o cale care pleaca din i catre k+1, atunci cea de la k+1 la j este mai buna. Stim ca cea mai cale de la i la j care foloseste doar noduri de la i la k+1 la j, atunci lungimea drumului va fi formata din concatenarea celei mai scurte cai de la i la k+1(folosind varfuri din multimea (1 k)) si cea mai scurta calea de la k+1 la j (de asemenea folosind noduri din multimea (1 k))

Astfel:

shortestPath(i,j,k)=min(shortestPath(i,j,k-1), shortestPath(i,k,k-1)+shortestPath(k,j,k-1));

shortestPath(i,j,0)=edgeCost(i,j);

Algoritmul calculeaza prima data shortestPath(i,j,1) pentru toate perechile (i,j), apoi folosind rezultatul pentru a gasi shortestPath(i,j,2) pentru toate perechile (i,j),etc. Acest process continua pana cand k=n si am gasit cea mai scurta cale pentru perechile (i,j) folosind un numar oarecare pentru nodurile intermediare.