Programarea algoritmilor pentru calcularea drumului min (Dijkstra, Prim, Kruskal)
Cel mai eficient algoritm cunoscut pentru problema
drumurilor optime cu o singură sursă este algoritmul lui Dijkstra, care poate fi descris în mai multe moduri: ca algoritm de
tip “greedy” cu o coadă cu priorităti, ca algoritm ce foloseste operatia de
“relaxare” (comună si altor algoritmi), ca algoritm cu multimi de vârfuri sau ca algoritm cu vectori. Diferentele
de prezentare provin din structurile de date utilizate. Se foloseste un vector
D astfel că d[i] este distanta minimă de
la 1 la i, dintre drumurile care trec
prin noduri deja selectate. O variabilă S de tip multime memorează numerele nodurilor
cu distantă minimă fată de nodul 1,
găsite până la un moment dat.
Initial S={1} si d[i]=cost[1][i], adică
se consideră arcul direct de la 1 la i ca drum minim între 1 si i. Pe măsură ce
algoritmul evoluează, se actualizează D si S.
S ={1} // S =multime
noduri ptr care s-a determinat dist. minima fata de 1
repetă cât timp S
contine mai putin de n noduri {
gaseste muchia (x,y)
cu x în S si y nu în S care face minim d[x]+cost(x,y)
adauga y la S
d[y] = d[x] + cost(x,y)
}
La fiecare pas din algoritmul Dijkstra:
- Se
găseste dintre nodurile j care nu apartin lui S acel nod "jmin" care
are distanta minimă fată de nodurile din S;
- Se
adaugă nodul "jmin" la multimea S;
- Se
recalculează distantele de la nodul 1 la nodurile care nu fac parte din S, pentru că distantele la nodurile
din S rămân neschimbate;
- Se
retine în p[j] numărul nodului precedent cel mai apropiat de nodul j (de pe
drumul minim de la 1 la j).
Pentru a ilustra modul
de lucru al algoritmului Dijkstra considerăm un graf orientat cu următoarele costuri
de arce:
(1,2)=5; (1,4)=2;
(1,5)=6;
(2,3)=3;
(3,2)=4; (3,5)=4;
(4,2)=2; (4,3)=7;
(4,5)=3;
(5,3)=3
Drumurile posibile
intre 1 si 3 si costul lor:
1-2-3 = 8; 1-4-3 = 9;
1-4-2-3 = 7; 1-4-5-3 = 8; 1-5-3 = 9;
Drumurile minime de la
1 la celelalte noduri sunt în acest graf:
1-4-2 cost 4
1-4-2-3 cost 7
1-4 cost 2
1-4-5 cost 5
De observat că într-un drum minim fiecare drum
partial este minim; astfel în drumul 1-4-2-3, drumurile partiale 1-4-2 si 1-4
sunt si ele minime.
Evolutia vectorilor D
si S pentru acest graf în cazul
algoritmului Dijkstra:
S
|
D[2]
|
D[3]
|
D[4]
|
D[5]
|
Nod sel
|
1
|
5
|
M
|
2
|
6
|
4
|
1,4
|
4
|
9
|
2
|
5
|
2
|
1,4,2
|
4
|
7
|
2
|
5
|
5
|
1,4,2,5
|
4
|
7
|
2
|
5
|
3
|
P[2]
|
P[3]
|
P[4]
|
P[5]
|
4
|
2
|
1
|
4
|
C[2]
|
P[2]
|
C[3]
|
P[3]
|
C[4]
|
P[4]
|
C[5]
|
P[5]
|
C[6]
|
P[6]
|
k
|
6
|
1
|
1
|
1
|
5
|
1
|
M1
|
1
|
M1
|
1
|
3
|
5
|
3
|
M2
|
1
|
5
|
1
|
6
|
3
|
4
|
3
|
6
|
5
|
3
|
M2
|
1
|
2
|
6
|
6
|
3
|
M2
|
3
|
4
|
5
|
3
|
M2
|
1
|
M2
|
6
|
6
|
3
|
M2
|
3
|
2
|
M2
|
3
|
M2
|
1
|
M2
|
6
|
3
|
2
|
M2
|
3
|
5
|
M2
|
3
|
M2
|
1
|
M2
|
6
|
M2
|
2
|
M2
|
3
|
Pas
|
Arc (Cost)
|
Acceptabil
|
Cost total
|
Afisare
|
1
|
1,3 (1)
|
da
|
1
|
1 – 3
|
2
|
4,6 (2)
|
da
|
3
|
4 – 6
|
3
|
2,5 (3)
|
da
|
6
|
2 – 5
|
4
|
3,6 (4)
|
da
|
10
|
3 – 6
|
5
|
1,4 (5)
|
nu
|
10
|
|
6
|
3,4 (5)
|
nu
|
10
|
|
7
|
2,3 (5)
|
da
|
15
|
2 – 3
|
Vectorul P va arăta în
final astfel:
Exemplu de functie
pentru algoritmul Dijkstra:
void dijkstra (Net
g,int p[]) { // Net este tipul abstract “graf cu costuri”
int d[M],s[M]; // s= noduri ptr care se stie
distanta minima
int dmin; int jmin,i,j;
for (i=2;i<=g.n;i++) {
p[i]=1; d[i]=carc(g,1,i); // distante
initiale de la 1 la alte noduri
}
s[1]=1;
for (i=2;i<=g.n;i++) { // repeta de n-1 ori
// caută nodul j ptr care d[j] este minim
dmin =MARE;
for (j=2;j<=g.n;j++) // determina
minimul dintre distantele d[j]
if (s[j]==0 && dmin > d[j]) {
// daca j nu e in S si este mai aproape de S
dmin =d[j]; jmin=j;
}
s[jmin]=1; // adauga nodul jmin la S
for (j=2;j<=g.n;j++) // recalculare
distante noduri fata de 1
if
( d[j] >d[jmin] + carc(g,jmin,j) ) {
d[j] =d[jmin] + carc(g,jmin,j);
p[j] =jmin; // predecesorul lui j pe drumul
minim
}
}
}
In programul principal
se apelează repetat functia "drum":
for(j=2;j<=n;j++)
drum (p,1, j); // afisare drum minim de la
1 la j
Afisarea drumului
minim pe baza vectorului "p" se poate face recursiv sau iterativ:
// drum minim intre i
si j - recursiv
void drum (int p[],
int i,int j) {
if (j != i)
drum (p,i,p[j]);
printf ("%d ",j);
}
// drum minim intre i si j - iterativ
void drum (int p[],
int i,int j){
int
s[M], sp=0; // s este o
stiva vector cu varful in sp
printf ("%d ",i); // primul nod de
pe calea i~j
while (j != i) { // pune pe stiva nodurile
precedente lui j
s[++sp]=j;
j=p[j]; // precesorul lui j
}
for( ; sp>=1;sp--) // afisare continut
stiva
printf("%d ",s[sp]);
}
Metoda de ajustare
treptată a lungimii drumurilor din vectorul D este o metodă de
"relaxare",
folosită si în alti
algoritmi pentru drumuri minime sau maxime: algoritmul Bellmann-Ford pentru drumuri
minime cu o singură sursă în grafuri cu costuri negative, algoritmul Floyd
pentru drumuri minime între oricare pereche de noduri s.a.
Prin relaxarea unei
muchii (v,w) se întelege ajustarea costului anterior al drumului către nodul w tinându-se
seama si de costul muchiei v-w, deci considerând si un drum către w care trece
prin v.
Complexitatea
algoritmului Dijkstra este O(n*n) si poate fi redusă la O(m*lg(n)) prin
folosirea unei cozi ordonate (min-heap) cu operatie de diminuare a cheii.
Pentru determinarea
unui arbore de acoperire de cost minim se cunosc doi algoritmi eficienti
având ca autori pe Kruskal
si Prim. Problema este de
a găsi pentru
un graf dat
arborele de acoperire
cu cost total
minim (MST=Minimum Spanning Tree) sau unul dintre ei, dacă sunt mai
multi.
Exemplu: graful
neorientat cu 6 noduri si următoarele arce si costuri:
(1,2)=6; (1,3)=1;
(1,4)=5;
(2,3)=5; (2,5)=3;
(3,4)=5; (3,5)=6;
(3,6)=4;
(4,6)=2;
(5,6)=6;
Arborele minim de
acoperire este format din arcele: (1,3),(3,6),(6,4),(3,2),(2,5) si are costul
total 1+5+3+4+2=15.
Algoritmul lui Prim
seamănă cu algoritmul Dijkstra pentru drumuri minime si foloseste o coadă cu priorităti de
arce care leagă
vârfuri din MST
cu alte vârfuri
(coada se modifică
pe măsură ce algoritmul evoluează). Algoritmul lui
Prim se bazează pe observatia următoare: fie S o submultime a vârfurilor
grafului si R submultimea V-S (vârfuri care nu sunt în S); muchia de cost minim
care uneste vârfurile din S cu vârfurile din R face parte din MST. La fiecare
pas se face o nouă tăietură în graful rămas si se determină un alt arc din MST;
proces repetat de n-1 ori (sau până când S este vidă). Solutia problemei este o
multime de arce, deci un vector de perechi de noduri, sau doi vectori de întregi
X si Y, cu semnificatia că o pereche x[i]-y[i] reprezintă un arc din MST. Este
posibilă si folosirea unui vector de întregi pentru arborele MST. Implementarea
mai eficienta a algoritmului Prim folosind 2 vectori:
p [i] = numărul
nodului din S cel mai apropiat de
nodul i din R
c [i] = costul arcului
dintre i si p[i]
La fiecare pas se
caută în vectorul “c” pentru a găsi nodul
k din R cel mai apropiat de nodul i din S. Pentru a nu mai folosi o
multime S, se atribuie lui c[k] o valoare
foarte mare astfel ca nodul k să nu mai fie luat in considerare în pasii
următori.
Multimea S este deci
implicit multimea nodurilor i cu c[i] foarte mare. Celelalte noduri formează multimea
R.
# define M 20 // nr maxim de noduri
# define M1 10000 // un nr. foarte mare (cost arc absent)
# define M2 (M1+1) // alt numar foarte mare (cost arc
folosit)
// alg. Prim pentru arbore minim de
acoperire
void prim (Net g, int
x[ ], int y[ ]){
int c[M], cmin;
int p[M], i,j,k;
int n=g.n; // n = nr de varfuri
for(i=2;i<=n;i++) {
p[i]=1;
c[i]=carc (g,1,i); // costuri initiale
}
for(i=2;i<=n;i++) {
// cauta nodul k cel mai apropiat de un nod
din mst
cmin = c[2]; k=2;
for(j=2;j<=n;j++)
if ( c[j] < cmin) {
cmin=c[j]; k=j;
}
x[i-1]=p[k]; y[i-1]= k; // retine muchie
de cost minim in x si y
c[k]=M2;
// ajustare costuri in U
for(j=2;j<=n;j++)
if (carc(g,k,j) < c[j] && c[j]
< M2) {
c[j]= carc(g,k,j); p[j] =k;
}
}
}
Evolutia vectorilor “c” si “p” pentru exemplul
dat este următoarea:
Au fost necesare două
constante mari: M1 arată că nu există un arc între două noduri, iar M2 arată că
acel arc a fost inclus în MST si că va fi ignorat în continuare.
Vectorul “p” folosit
în programul anterior corespunde reprezentării unui arbore printr-un singur vector,
de predecesori.
Complexitatea
algoritmului Prim cu vectori este O(n*n), dar poate fi redusă la O(m*lg(n))
prin folosirea unui heap pentru memorarea costurilor arcelor dintre U si V.
Ideea algoritmului Kruskal
este de a alege la fiecare pas arcul de cost minim dintre cele rămase (încă
neselectate), dacă el nu formează ciclu cu arcele deja incluse în MST
(selectate). Conditia ca un arc (x,y) să nu formeze ciclu cu celelalte arce
selectate se poate exprima astfel:
nodurile x si y trebuie să se afle în componente conexe diferite.
Initial fiecare nod formează o componentă conexă, iar apoi o componentă conexă
contine toate nodurile
acoperite cu arce
din MST, iar
nodurile neacoperite formează
alte componente conexe.
Algoritmul Kruskal
pentru găsirea unui arbore de acoperire de cost minim foloseste două tipuri abstracte
de date: o coadă cu priorităti si o colectie de multimi disjuncte si poate fi descris
astfel:
citire date si creare coada de arce
repetă {
extrage arcul de cost minim din coada
dacă arc acceptabil atunci {
afisare arc
actualizare componente conexe
}
} până când toate nodurile conectate
Un arc care leagă două noduri dintr-o aceeasi
componentă conexă va forma un ciclu cu arcele selectate anterior si nu poate fi
acceptat. Va fi acceptat numai un arc care leagă între ele noduri aflate în
două componente conexe diferite.
Pentru reteaua cu 6
noduri si 10 arce (1,2)=6; (1,3)=1;
(1,4)=5; (2,3)=5; (2,5)=3;
(3,4)=5; (3,5)=6; (3,6)=4;
(4,6)=2; (5,6)=6
Evolutia algoritmului
Kruskal este următoarea:
Toate nodurile din
graf trebuie să se afle în componentele conexe. Initial sunt atâtea componente (multimi)
câte noduri există. Atunci când un arc este acceptat, se reunesc cele două multimi (componente) care contin
extremitătile arcului în una singura; în felul acesta numărul de componente conexe
se reduce treptat până când ajunge egal cu 1 (toate nodurile legate într-un
graf conex care este chiar arborele de acoperire cu cost minim).
Evolutia componentelor
conexe pentru exemplul anterior:
Pas Componente conexe
1
{1},
{2},{3},{4},{5},{6}
2 {1,3}, {2},{4},{5},{6}
3 {1,3}, {2,5}, {4,6}
4 {1,3,4,6}, {2,5}
7 {1,2,3,4,5,6}
In programul următor graful este un vector de
arce, ordonat crescător după costuri înainte de a fi folosit. Exemplu:
typedef struct { int
v,w,cost ;} Arc;
// compara arce dupa cost (ptr qsort)
int cmparc (const void
* p, const void* q) {
Arc * pp =(Arc*) p; Arc *qq=(Arc*) q;
return pp->cost -qq->cost;
}
// algoritmul Kruskal
void main ( ) {
DS ds;
Arc arce[M], a;
int x,y,n,na,mx,my,nm,k;
printf ("nr.noduri în graf:
"); scanf ("%d", &n);
initDS (ds,n); // ds = colectie de multimi disjuncte
printf ("Lista de arce cu costuri:
\n");
nm=0; // nr de muchii in graf
while ( scanf
("%d%d%d",&a.v,&a.w,&a.cost) > 0)
arce[nm++]=a;
qsort (arce, nm, sizeof(Arc), cmparc); // ordonare lista arce
k=0; // nr arc extras din coada
for ( na=n-1; na > 0; na--) {
a=arce[k++]; // următorul arc de cost
minim
x=a.v; y=a.w; // x, y = extremitati arc
mx= findDS (ds,x); my=findDS (ds,y);
if (mx !=my ) { // daca x si y in
componente conexe diferite
unifDS (ds,x,y); // atunci se reunesc
cele doua componente
printf ("%d - %d \n",x,y); //
si se scrie arcul gasit ptr mst
}
}
}
