|
ALGORITMUL LUI DIJKSTRA
Algoritmul lui Dijkstra pentru determinarea drumurilor minime cu origine unica este un principiu asemanator algoritmului prezentat in lucrarea anterioara, de determinarea adrumurilor minime cu origine unica prin cautare bazata pe prioritate.
Se considera un graf orientat ponderat, G=(N,A), fiecarui arc a=(i,j) din A ii este asociat un cost COST[i,j]. Algoritmul utilizeaza o structura de date multime M in care mentine nodurile din N pentru care cea mai scurta distanta pana la nodul origine e deja cunoscuta.Aceasta multime M corespunde multimii nodurior "vizitate" deja. M se initializeaza cu nodul de start.
Algoritmul cuprinde mai multe iteratii, in cadrul fiecarei iteratii se selecteaza un nod x din multimea N-M, cu proprietatea ca x este cel mai aproape de nodul de start si se trece in multimea M a nodurilor vizitate. Se verifica apoi pentru fiecare nod y ramas in N-M daca nu exista un drum mai scurt de la nodul origine spre y, drum care trece prin x.
Algoritmul utilizeaza un tablou D, D[i] fiind lungimea celui mai scurt drum de la origine la nodul numarul i la un moment dat. Initial, D[i]=COST[origine,i]. Pe masura ce se gasesc noduri x,y astfel incat D[y]>D[x]+COST[x,y], D[y] este redus. La terminarea algoritmului, D[i] va contine lungimea drumului minim de la origine la i.
procedure Dijkstra;
{Date de intrare: Graful orientat ponderat G=(N,A) si nodul
nod_origine}
{Date de iesire: pentru fiecare nod i, D[i] este lungimea
calculata a drumului minim de la nod_origine la i}
begin
* initializeaza multimea M a nodurilor vizitate,
introduce nod_origine in M
* pentru toate nodurile i, initializeaza lungimea
drumului minim pana la i (D[i]) cu lungimea
arcului direct de la nod_origine la i
while ( * mai exista noduri in N-M ) do
begin
* alege un nod x apartinand multimii
N - M astfel incat D[x] sa fie
minim si il adauga pe x la M;
for * fiecare nod y din N-M do
* test daca drumul de la nod_origine
la y folosind ca punct intermediar
nodul x este mai scurt decit cel memorat
anterior, si daca da, actualizeaza D[y] in forma
D[y] := min(D[y],D[x] + COST[x,y]);
end
end; {Dijkstra}
In vederea reconstructiei traseurilor drumurilor minime de la nodul de start la fiecare nod al grafului, se poate utiliza un alt tablou Parinte de noduri, in care Parinte[x] contine nodul care precede nodul x in cadrul drumului minim. Initial, Parinte[i]= 1 pentru toate nodurile, cu exceptia nodului 1(nodul de start). Elementul Parinte[y] va fi actualizat in momentul actualizarii lui D[y], daca D[x]+COST[x,y]< D[Y]
G. grafului al minim acoperire de arbore un
contine Parinte Tabloul Parinte[y]:="x;" atunci> Problema determinarii drumurilor minime corespunzatoare unui nod precizat al unui graf se reduce de fapt la determinarea unui arbore de acoperire care are drept radacina nodul in cauza.
Algoritmul lui Dijkstra opereaza asupra grafurilor dense orientate, reprezentate prin matrici de adiacenta. Se executa n iteratii pentru selectarea tutoror nodurilor, iar in cadrul fiecarei iteratii se face o parcurgere a tuturor nodurilor inca neselectate y pentru ajustarea tabloului D. Performanta algoritmului este deci O(n2).
Daca a este mult mai mic decat n2, este mai indicat ca in reprezentarea grafului sa se foloseasca liste de adiacente, respectiv o coada bazata pe prioritate pentru a pastra nodurile multimii N-M. In acest caz, algoritmul lui Dijkstra devine algoritmul de determinare a drumurilor minime cu origine unica folosind cautarea bazata pe prioritate, prezentat in lucrarea anterioara.
|
