[Graphe] Algorithme de Floyd

Algorithme de Floyd permet de calculer les plus courtes distances entre toute paire de sommets du graphe

Le graphe est un graphe orienté valué

Principe:

  • On construit une matrice de dimension n * m
  • On initialise les coefficients d[x,y] de la matrice avec le poids des arcs v[x,y]
  • A la fin des itérations, le coefficient d[x,y] contient la longueur du plus court chemin menant du sommet x au sommet y
  • S’il n’y a pas de chemin, alors d[x,y] = +∞
Pour tout sommet x Faire
	d[x,x] := 0;
	Pour tout sommet y <> x Faire
		Si l’arc (x,y) existe Alors
			d[x,y] := v[x,y];
		Sinon
			d[x,y] := +∞;
		Fin Si
	Fin Pour
Fin pour

Pour tout sommet z Faire
	Pour tout sommet y Faire
		Pour tout sommet x Faire
			d[x,y] := min(d[x,y], d[x,z] + d[z,y]);
		Fin pour
	Fin pour
Fin pour

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 :