Metoda Dijkstra

1) Fiecărui nod iÎV i s-a asociat o variabilă d(i) numită în continuare eticheta nodului i. Prin definiție d(s) = 0 . În oricare moment al aplicării algoritmului variabilei d(i) reține valoarea unui drum de la s la i găsit de algoritm până în acel moment. Dacă algoritmul nu a găsit încă un drum de la s la i variabila d(i) are valoarea +∞. La finalul aplicării metodei, eticheta indică valoarea celui mai „scurt” drum de la nodul s la nodul i. Pe parcursul aplicării algoritmului etichetele se corectează în sensul micsorării valorilor lor. În momentul în care o etichetă d(i) atinge valoarea minimă ea devine permanentă.

Metodele de rezolvare a problemei determinării drumului de valoare minimă între două noduri ale

unui graf sunt procedee de etichetare care se împart în două clase:

- metode cu etichetare permanentă (la fiecare iterație se identifică un nod a cărui etichetă se

permanentizează - valoarea ei nu se va mai modifica până la finalul rezolvării); si

- metode cu etichetare temporară (etichetele tuturor nodurilor au valori temporare care devin

permanente doar la finalul rezolvării).

Metodele aparținând primei clase se aplică numai grafurilor cu valori (costuri) nenegative ale

muchiilor, în timp ce metodele aparținând celei de a doua clase se aplică grafurilor cu valori (costuri)

negative ale muchiilor. Algoritmul Dijkstra aparține primei clase.

2) Fiecărui nod iÎV diferit de s i se asociază o altă variabilă PRED(i) numită INDICATOR DE PRECEDENȚĂ cu următoarea semnificație: în oricare moment al aplicării algoritmului PRED(i) conține ultimul nod dinaintea lui i pe drumul de la s la i găsit de algoritm până în acel moment. Atâta timp cât un asemenea drum nu a fost găsit d(i) = +î , indicatorul PRED(i) nu este definit el fiind o locație vidă (PRED(i) = Æ).

3) Inițializăm o listă P în care vom include toate nodurile iÎG pentru care algoritmul a găsit un drum de valoare minimă de la i la s (lista nodurilor cu eticheta declarată permanentă). La start P se reduce la nodul de plecare s.

4) Inițializăm o listă T în care vom include toate nodurile jÎV care sunt vecine cu noduri din lista P: un nod j este vecin cu i dacă arcul (i, j) este permis. T este lista nodurilor cu eticheta declarată temporară.

Nodurile cu etichetă permanentă din lista P se selectează din lista T a nodurilor candidate. Corectarea unei etichete se face după următoarea schemă echivalentă (figura).

Referitor la un arc permis i, jU cu valoarea vi, j- - 0 presupunem că algoritmul a găsit un

drum λ de la s la i a cărui valoare e reținută în eticheta d i- si un drum μ de la s la j a cărui valoare se găseste

în locația d- j. Figura 1.14 pune în evidență cele două drumuri de la s la j.

- drumul - - i, j- de valoare di- vi, j;

- ,,vechiul” drum μ de valoare d- j.

Dacă d i- vi, j- - - d - j- atunci primul drum are o valoare mai mică si ca urmare va fi reținut de

algoritm ca fiind cel mai bun drum de la s la j găsit până în acest moment. Memorarea acestui nou drum se

face prin corectarea etichetei d- j- care ia valoarea d- j- - di- - vi, j- si actualizarea indicatorului de

precedență PRED (j): PRED (j) = i.

Cu aceste pregătiri trecem la prezentarea algoritmului Dijkstra.