[Graphe] Algorithme de Lester Ford

Algorithme de Lester Ford permet de calculer les plus courts chemins à partir d’un sommets donné.

  • Graphe orienté valué
  • Graphe connexe

Si le graphe n’a pas de circuit absorbant, le problème admet une solution fournie par l’algorithme.

  • s = le sommet de départ des plus courts chemins
  • d[x] = fonction qui donne la valeur du plus court chemin entre le sommet s et le sommet x du graphe
  • p[x] = prédécesseur du sommet x dans le plus court chemin de s à x
  • p[.] et d[.] sont évalués au fur et à mesure du déroulement de l’algorithme
d[s] := 0;
p[s] := 0;
Pour tout sommet x <> s faire
	d[x] := + ∞;
	p[x] := NIL;
Fin pour

Tant qu'il existe un arc(x,y) du graphe tel que d[x] + v[x,y] < d[y] faire
	d[y] := d[x] + v[x,y];
	p[y] := x;
Fin tant que

S’il n’y a pas de circuit absorbant,

  • l’algorithme s’arrête après un certain nombre d’itérations
  • le résultat est la fonction d[.] qui donne la valeur des plus courts chemins au sommet s

p[.] forme une arborescence

  • Racine « s« 
  • Arborescence des plus courts chemins

One comment

  1. […] Reprend l’algorithme de Ford […]

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 :