DRUMURI MINIME SI MAXIME IN GRAFURIConsiderăm un graf orientat G=(X,U) cu n noduri, în care fiecărui arc îi este asociat un număr întreg numit cost. Semnificaţia acestui cost poate fi foarte variată, în funcţie de domeniul pe care îl descrie graful. De exemplu, dacă graful reprezintă harta unui oraş în care arcele sunt străzile, iar nodurile sunt intersecţiile dintre stăyi, atunci putem vorbi despre costul deplasării unui automobil între două intersecţii, de-a lungul unei străzi. Acesta s-ar putea măsura în cantitatea de benzină consumată, calculată prin prisma lungimii străzii în m sau in km.MATRICEA COSTURILORPentru evidenţierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.există două forme ale acestei matrici:Forma a): Fiecare element a[i,j] poate fi:-c, dacă există un arc de cost c>0 între nodurile i şi j;-0, dacă i=j;-+infinit, dacă nu există arc între nodurile i şi j.Forma b): Este absolut similară, cu singura deosebire că în loc de +infinit avem -infinit.Forma a)se foloseşte pentru determinarea drumurilor de cost minim între două noduri, iar forma b) este utilizată în aflarea drumurilor de cost maxim.Dacă dorim să citim matricea costurilor, evident că nu putem introduce de la tastatură “+infinit”! În loc de “+infinit” vom da un numar de la tastatură foarte mare.Problema determinării drumului minim/ maxim între două noduri face obiectul algoritmului următor.Algoritmul Roy-FloydSe consideră un graf orientat cu n noduri, pentru care se dă matricea costurilor în forma a). Se cere ca, pentru fiecare pereche de noduri (i, j), să se tipărească costul drumului minim de la i la j.Plecăm de la următoarea idee: dacă drumul minim între două noduri oarecare i şi j trece printr-un nod k, atunci drumurile de la i la k şi de la k la j sunt la rândul lor minime. Pentru fiecare pereche de noduri (i, j ), cu i, j apartinand multimii {1,2,…,n}, procedăm astfel:
Dăm lui k pe rând valorile 1,2,…,n, pentru ca nodul k despre care vorbeam mai sus poate fi, cel puţin teoretic, orice nod al grafului. Pentru fiecare k:
dacă suma dintre costul drumului de la i la k şi costul drumului de la k la j este mai mică decât costul drumului de la i la j{a[i, k]+a[k, j], atunci drumul iniţial de la i la j este înlocuit cu drumul indirect i-k-j. această înlocuire fireşte că se va opera ca atare în matrocea costurilor: {a[i, j]:=a[i, k]+a[k, j]}.
Prezentăm în continuare procedura generare care conţine algoritmul descris:Procedure generare;var i,j,k:integer;beginfor k:=1 to n dofor i:=1 to n dofor j:=1 to n doif a[i, k]+a[k, j]end;
Observatii
Drumurile minime între toate nodurile se regăsesc la sfarsitul algoritmului tot în matricea costurilor, care a suferit n trasformări, pentru k=1,2,…,n.
Unele elemente pot fi +infinit, iar pentru simularea lui +infinit am spus că se introduce un număr întreg foarte mare. Prin adunări repetate a două numere întregi foarte mari putem ajunge la un rezultat care depăşeşte cea mai mare valoare posibilă de tipul integer. De aceea, recomandăm ca elementele matricei costurilor să fie de tipul longint.
În cazul în care problema cerea pentru fiecare pereche de noduri (i, j) costul drumului maxim, modificările necesare ar fi minore: