ALGORITMI PENTRU PRELUCRAREA GRAFURILOR
1.Continutul lucrarii
In lucrare sunt prezentati algoritmii lui Dijkstra si Floyd pentru gasirea cailor de cost minim între doua noduri precizate, respectiv între 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 vârf
Se considera un graf orientat G =(V, E) etichetat, în care fiecare arc are ca etichet 525j94f a un numar nenegativ numit cost. Graful se reprezinta în memorie prin matricea de adiacente etichetata, care se mai numeste matricea costurilor.
Fiind date doua vârfuri, 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 vârfuri j V, pentru care exista cel putin un drum de la sursa la j. Initial S =.
- la fiecare pas, se adauga la S un vârf a carui distanta fata de un vârf din S este minima.
Pentru a înregistra caile minime de la sursa la fiecare vârf se utilizeaza un tablou TATA, în care TATA[k] pastreaza vârful anterior lui k pe calea cea mai scurta.
In descrierea algoritmului se fac urmatoarele notatii:
- n numarul vârfurilor multimii V;
- multimea S se reprezinta prin vectorul caracteristic ( elementele sale sunt S[i]=1, daca i S si S[i]=0, daca i S;
- vectorul DISTANTE de n elemente al distantelor minime de la sursa la fiecare vârf;
- matricea de costuri COST de nxn elemente: COST[ i ][j]=c>0 daca ( i ,j) E, 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 */
for (pas=1;pas<=n-1;pas++)
}
}
Vectorul TATA contine vârfurile accesibile din vârfurile sursa. El permite reconstruirea drumurilor de la vârful sursa la oricare vârf accesibil. Pentru vârfurile inaccesibile din vârful sursa vom avea S[i]=0 si DISTANTE[i]=INFINIT.
2.2.Caile de cost minim din oricare vârf
Algoritmul prezentat la 2.1. poate fi repetat din nodurile unui graf. Acest lucru permite calculul unui tablou al drumurilor minime între toate perechile de vârfuri ale grafului. In continuare se prezinta un algoritm mai simplu, algoritmul lui Floyd.
Algoritmul lui Floyd consta în gasirea costurilor minime între oricare doua vârfuri i, j V. Aceste costuri minime se pastreaza în matricea A. Matricea A este initial egala cu matricea costurilor. Calculul distantelor minime se face în n iteratii, n fiind numarul vârfurilor. La iteratia k, A[i][j] va avea ca valoare cea mai mica distanta intre i si j pe cai care nu contin vârfuri peste k (exceptând capetele i si j). Se utilizeaza formula urmatoare:
Aij(k)= min (Aij(k-1),Aik(k-1)+Akj(k-1)).
Deoarece Aik(k)=Aik(k-1) si Akj(k)=Akj(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 vârf k ce a condus la distanta minima A[i][j]. Daca P[i][j]==0, atunci arcul (i, j) este calea minima între i si j.
Pentru a afisa vârfurile intermediare aflate pe calea cea mai scurta între 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) R i se asociaza un cost c[i][j]>0. Problema consta în a determina un graf partial conex A = (N, T), astfel încât suma costurilor muchiilor din T sa fie minima. Se observa imediat ca acest graf partial este chiar arborele de acoperire.
Algoritmul lui Prim consta în 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, w W si u N-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 în T.
Acest algoritm are urmatoarea descriere:
void algoritm_Kruskal(int n)
;
while (T nu este arbore de acoperire)
}
Problema mai dificila în algoritm consta în 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 vârf al unui graf orientat. Se va construi si afisa arborele având ca radacina vârful sursa. Care este performanta algoritmului în ceea ce priveste timpul de calcul?
3.2.Sa se implementeze algoritmul lui Floyd de gasire a cailor de cost minim din oricare vârf al unui graf neorientat. Se vor afisa caile de cost minim între doua vârfuri, date de la tastatura. Care este performanta algoritmului în 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 în ceea ce priveste timpul de calcul între algoritmul lui Kruskal si cel al lui Prim.
|
