Matricea costurilor

Se numeste graf ponderat ("weighted graph") un graf in cadrul cãruia fiecãrui arc ii este asociatã o valoare. Valoarea asociata arcului are semnificaþia de "cost" a legaturii intre cele 2 noduri sau de "distanta" intre noduri.

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii) memorat prin matricea ponderilor. Se cere ca pentru doua noduri x,y citite sa se determine lungimea minima a lantului de la x la y.

Astfel:

Initial matricea ponderilor pentru nodurile 1 si 4 va retine 10. Se observa ca lantul 1,2,3,4 determina o suma a costurilor mai mica: 2+3+1=6. Lungime minima a lantului de la 1 la 4 este 6.

Algoritmul:
-se genereaza matricea ponderilor:
0 2 pinf 10 pinf
2 0 3 pinf pinf
pinf 3 0 1 8
10 pinf 1 0 pinf
pinf pinf 8 pinf 0
Unde pinf reprezinta plus infinit

-se incearca pentru oricare pereche de noduri i,j sa se obtina “drumuri” mai scurte prin noduri intermediare k (kÎ1…n).

Acest lucru se determina comparand “lungimea” lantului a[i,j] cu lungimea lantului care trece prin k si daca:
a[i,j] > a[i,k]+a[k,j] atunci se atribuie: a[i,j] ¬ a[i,k]+a[k,j]

Astfel generarea matricii drumurilor optime se realizeaza cu urmatoarea secventa:

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];

Se obtine:
0 2 5 6 13
2 0 3 4 11
5 3 0 1 8
6 4 1 0 9
13 11 8 9 0


In continuare, dupa determinarea matricii lanturilor optime, pentru doua noduri citite x, y se cere sa se reconstituie un lant optim de la x la y (pot fi mai multe solutii).

Solutie:
-se determina daca exista un lant de la x la y (ar putea sa nu existe un astfel de lant daca graful nu este conex):
cand a[x,y] ¹¥
-se descompune “drumul” de la x la y prin ca atunci cand: a[x][y]=a[x][k]+a[k][y];
- pentru un astfel de algoritm se utilizeaza strategia Divide et Impera