[Graphe] Algorithme de Dijkstra

Quand les poids des arêtes sont positifs, on peut utiliser l’algorithme de Dijkstra (Prononcer Dèxtra ^_^ )

  • On ajoute une règle établissant l’ordre dans lequel les arcs du graphe sont examinés
  • ATTENTION: s’il y a des poids négatifs l’algorithme peut donner des résultats erronés

Principe:

  • Graphe orienté connexe avec des poids >=0 et pouvant contenir des circuits: pas de circuit absorbant
  • s = sommet source
  • d[x] = longueur du plus court chemin de s à x: vaut +∞ s’il n’y pas de chemin de s à x
d[s] := 0;
L := X;  // Ensemble des sommets du graphe
Pour tout sommet x <> s faire
	d[x] := +∞;
	p[x] := NIL;
Fin pour

TantQue L non vide faire
	Soit x de L de valeur d[x] minimale parmi les sommets de L
	Pour tout arc (x,y) faire
		Si (d[x]+v[x,y] < d[y]) Alors
			d[y] := d[x] + v[x,y];
			p[y] := x;
		Fin Si
	Fin pour
	L := L – {x};
Fin TantQue

Laisser des commentaires:

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :