Algoritmul lui Dijkstra

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.

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;
• în mod repetat:
  • 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 îmbunătățește costul d[x] (arcul relaxează drumul);
    
• alegerea acestor noduri se termină când toate nodurile au fost adăugate în F (s-au determinat costurile drumurilor 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;

Exercițiu

Aplicați algoritmul lui Dijkstra pentru graful de mai jos și s=1:

Secvență C++

În secvența de mai jos, considerăm un graf orientat cu n noduri, reprezentat prin matricea de adiacență a[][], în care a[i][j]=INFINIT dacă nu există arcul (i,j).

#define INFINIT 1000000000
...
//nodul sursa este s
...
for(i =1 ; i <= n ; i ++ )
{
	f[i] = 0;
	d[i] = a[s][i];
}

f[s] = 1, d[s] = 0;
d[0] = INFINIT; // pentru determinarea nodului cu costul minim
for(int k = 1 ; k < n ; ++k)
{
	int pmax = 0;
	for(i = 1 ; i <= n ; ++i)
		if(f[i] == 0 && d[i] < d[pmax])
			pmax = i;

	if(pmax > -1)
	{
		f[pmax] = 1;
		for(i = 1; i <= n ; ++i)
			if(f[i] == 0 && d[i] > d[pmax] + a[pmax][i])
				d[i] = d[pmax] + a[pmax][i];
	}
}

Citește mai departe