Algoritmi pentru prelucrarea grafurilor

ALGORITMI PENTRU PRELUCRAREA GRAFURILOR

1.Continutul lucrarii

In lucrare sunt prezentati algoritmii lui Dijkstra si Floyd pentru gasirea cailor de cost minim intre doua noduri precizate, respectiv intre oricare doua noduri ale unui graf si algoritmii lui Kruskal si Prim pentru gasirea arborelui de cost minim de acoperire a unui graf.

2.Consideratii teoretice

2.1.Caile de cost minim dintr-un varf

Se considera un graf orientat G =(V, E) etichetat, in care fiecare arc are ca eticheta un numar nenegativ numit cost. Graful se reprezinta in memorie prin matricea de adiacente etichetata, care se mai numeste matricea costurilor.

Fiind date doua varfuri, unul sursa si unul destinatie, se cere gasirea drumului de cost minim de la sursa la destinatie. Algoritmul lui Dijkstra de rezolvare a acestei probleme consta in urmatoarele:

- se pastreaza o multime S de varfuri jIV, pentru care exista cel putin un drum de la sursa la j. Initial S =.

- la fiecare pas, se adauga la S un varf a carui distanta fata de un varf din S este minima.

Pentru a inregistra caile minime de la sursa la fiecare varf se utilizeaza un tablou TATA, in care TATA[k] pastreaza varful anterior lui k pe calea cea mai scurta.

In descrierea algoritmului se fac urmatoarele notatii:

- n numarul varfurilor multimii V;

- multimea S se reprezinta prin vectorul caracteristic ( elementele sale sunt S[i]=1, daca iIS si S[i]=0, daca i S;

- vectorul DISTANTE de n elemente al distantelor minime de la sursa la fiecare varf;

- matricea de costuri COST de nxn elemente: COST[ i ][j]=c>0 daca ( i ,j)IE, COST[i][j]=0 daca i =j si COST[i][j]=+ daca (i, j) E;

- vectorul TATA.

Algoritmul lui Dijkstra este urmatorul:

#define NMAX .

#define INFINIT .

float DISTANTE[NMAX];

float COST[NMAX][NMAX];

int TATA[NMAX];

int S[NMAX];

void DIJKSTRA(int n,int sursa)

/*introducere sursa in S*/

S[sursa]=1;

TATA[sursa]=0;

DISTANTE[sursa]=0;

/*construire vectori DISTANTE si TATA */

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

for (pas=1;pas<=n-1;pas++)

}

}

Vectorul TATA contine varfurile accesibile din varfurile sursa. El permite reconstruirea drumurilor de la varful sursa la oricare varf accesibil. Pentru varfurile inaccesibile din varful sursa vom avea S[i]=0 si DISTANTE[i]=INFINIT.

2.2.Caile de cost minim din oricare varf

Algoritmul prezentat la 2.1. poate fi repetat din nodurile unui graf. Acest lucru permite calculul unui tablou al drumurilor minime intre toate perechile de varfuri ale grafului. In continuare se prezinta un algoritm mai simplu, algoritmul lui Floyd.

Algoritmul lui Floyd consta in gasirea costurilor minime intre oricare doua varfuri i, jIV. Aceste costuri minime se pastreaza in matricea A. Matricea A este initial egala cu matricea costurilor. Calculul distantelor minime se face in n iteratii, n fiind numarul varfurilor. La iteratia k, A[i][j] va avea ca valoare cea mai mica distanta intre i si j pe cai care nu contin varfuri peste k (exceptand capetele i si j). Se utilizeaza formula urmatoare:

A_ij^(k)= min (A_ij^(k-1),A_ik^(k-1)+A_kj^(k-1)).

Deoarece A_ik^(k)=A_ik^(k-1) si A_kj^(k)=A_kj^(k-1) se poate utiliza o singura copie a matricii A.

Algoritmul lui Floyd este urmatorul:

#define NMAX .

float C[NMAX][NMAX];  /*matricea costurilor*/

float A[NMAX][NMAX];

void FLOYD(int n)

Pentru a pastra caile minime, se utilizeaza un tablou aditional P, unde P[i][j] tine acel varf k ce a condus la distanta minima A[i][j]. Daca P[i][j]==0, atunci arcul (i, j) este calea minima intre i si j.

Pentru a afisa varfurile intermediare aflate pe calea cea mai scurta intre i si j se poate proceda conform algoritmului urmator:

void CALE(int i, int j)

}

2.3.Arborele de acoperire de cost minim

Fie G =(N, R) un graf neorientat conex. Fiecarei muchii (i, j)IR i se asociaza un cost c[i][j]>0. Problema consta in a determina un graf partial conex A = (N, T), astfel incat suma costurilor muchiilor din T sa fie minima. Se observa imediat ca acest graf partial este chiar arborele de acoperire.

Algoritmul lui Prim consta in urmatoarele:

- se porneste cu o submultime W, formata din nodul de plecare si multimea T  vida;

- la fiecare iteratie, se selecteaza muchia (w, u) cu cel mai mic cost, wIW si uIN-W. Se adauga u la W si (w, u) la T. In final, W va contine toate nodurile din N, iar T va contine muchiile arborelui de  acoperire minimal.

void algoritm_PRIM(int n)

; //se pleaca din nodul 1

T=; //multimea vida

while (W!=N)

}

Un alt algoritm apartine lui Kruskal. In acest caz, muchiile sunt ordonate crescator dupa cost. Arborele de acoperire va contine n-1 muchii. La fiecare pas se alege muchia de cost minim care nu formeaza ciclu cu muchiile aflate deja in T.

Acest algoritm are urmatoarea descriere:

void algoritm_Kruskal(int n)

;

while (T nu este arbore de acoperire)

}

Problema mai dificila in algoritm consta in verificarea daca o muchie creeaza ciclu in T.

3.Mersul lucrarii

3.1.Sa se implemeteze algoritmul lui Dijkstra de gasire a cailor de cost minim dintr-un varf al unui graf orientat. Se va construi si afisa arborele avand ca radacina varful sursa. Care este performanta algoritmului in ceea ce priveste timpul de calcul?

3.2.Sa se implementeze algoritmul lui Floyd de gasire a cailor de cost minim din oricare varf al unui graf neorientat. Se vor afisa caile de cost minim intre doua varfuri, date de la tastatura. Care este performanta algoritmului in ceea ce priveste timpul de calcul?

3.3..Sa se implementeze algoritmul lui Prim de gasire a arborelui de acoperire a unui graf neorientat.

3.4.Sa se implementeze algoritmul lui Kruskal de gasire a arborelui de acoperire a unui graf neorientat. Sa se faca o comparatie in ceea ce priveste timpul de calcul intre algoritmul lui Kruskal si cel al lui Prim.