Consideram un graf orientat G=(X,U) cu n noduri, în care fiecarui arc îi este asociat un numar întreg numit cost. Semnificatia acestui cost poate fi foarte variata, în functie de domeniul pe care îl descrie graful. De exemplu, daca graful reprezinta harta unui oras în care arcele sunt strazile iar nodurile sunt intersectiile dintre stayi, atunci putem vorbi despre costul deplasarii unui automobil între doua intersectii, de-a lungul unei strazi. Acesta s-ar putea masura în cantitatea de benzina consumata, calculata prin prisma lungimii strazii în m sau in km.



Pentru evidentierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.exista doua forme ale acestei matrici:
Forma a): Fiecare element a[i,j] poate fi:
-c, daca exista un arc de cost c>0 între nodurile i si j;
-0, daca i=j;
-+(, daca nu exista arc între nodurile i si j.
Forma b): Este absolut similara, cu singura deosebire ca în loc de +( avem -(.
Forma a)se foloseste pentru determinarea drumurilor de cost minim între doua noduri, iar forma b) este utilizata în aflarea drumurilor de cost maxim.
Daca dorim sa citim matricea costurilor, evident ca nu putem introduce de la tastatura “+(”! În loc de “+(” vom da un num[r de la tastatura foarte mare.
Problema determinarii drumului minim/ maxim între doua noduri face obiectul algoritmului urmator.


Algoritmul Roy-Floyd
Se considera un graf orientat cu n noduri, pentru care se da matricea costurilor în forma a). Se cere ca, pentru fiecare pereche de noduri (i, j), sa se tipareasca costu drumului minim de la i la j.
Plecam de la urmatoarea idee: daca drumul minim între doua noduri oarecare i si j trece printr-un nod k, atunci drumurile de la i la k si de la k la j sunt la rândul lor minime. Pentru fiecare pereche de noduri (i, j ), cu i, j ({1,2,…,n}, procedam astfel:
Dam lui k pe rând valorile 1,2,…,n, pentru ca nodul k despre care vorbeam mai sus poa