[Graphe] Algorithme de Bellman

Algorithme de Bellman calcul des plus courts chemins à partir d’un sommet s donné dans un graphe orienté valué sans circuit

s est relié à tous les sommets du graphe

Principe:

Reprend l’algorithme de Ford

  • Ajoute une règle supplémentaire déterminant un ordre d’examen des arcs du graphe
  • Dans l’algorithme de Bellman, le traitement d’un sommet i consiste à examiner successivement tous les arcs d’origine i
  • Tous les sommets du graphe seront traités une fois et une seule, suivant une numérotation topologique des sommets
d[1] := 0;
Pour tout i de 2 à n faire
	d[i] := +∞;
	p[i] := NIL;
Fin pour
Pour i de 1 à (n-1) faire
	Pour tout arc (i,j) faire
		Si (d[i] + v[i,j] < d[j]) Alors
			d[j] := d[i] + v[i,j];
			p[j] := i;
		Fin Si
	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 :