Aspecte generale
Algoritmul lui Dijkstra determină pentru un nod dat într-un graf orientat cu costuri costurile minime ale drumurilor care au acel nod ca extremitate inițială.
Mai precis, pentru un nod s – sursă, algoritmul determină pentru orice nod x costul minim al unui drum de la s la x.
Strategie
Strategia algoritmului lui Dijkstra este una de tip Greedy
- se menține un tablou d[], în care d[x] reprezintă costul minim curent (eventual infinit) al unui drum de la s la x;
- se menține o mulțime F de noduri k pentru care s-a determinat costul minim final d[k]
- inițial în F se adaugă doar nodul s, pentru care d[s]=0; pentru nodurile x adiacente cu s, d[x]=c[s,x], unde c[x,y] este costul arcului (x,y), iar pentru celelalte noduri costul d[] se inițializează cu INFINIT;
- alegem un nod din afara mulțimii F, nodul k pentru care costul drumului d[k] este minim și finit;
- adăugăm nodul găsit k în F;
- pentru fiecare arc (k,x) cu x din afara mulțimii F stabilim dacă acest arc se îmbunătățește costul d[x] (arcul relaxează drumul);
- ultimii trei pași se repetă până când toate nodurile au fost adăugate în F (s-au determinat costurile drumurile de la s la fiecare nod al grafului) sau când nu mai există noduri x din afara mulțimii F pentru care d[x] este finit
Reprezentare vizuală
Exemplu C++ (folosește priority que din STL)
