Algorithme de Ford-Bellman

Sommaire du document

Fonctionnalités de l'algorithme de Ford-Bellman

Nous retrouvons cet algorithme sous le nom de Ford-Bellman, ou aussi Bellman-Ford.

• Ford-Bellman est un algorithme de recherche de chemin extrême.
• Ford-Bellman est utilisé sur des graphes pondérés^[1]
• Nous pouvons utiliser l'algorithme de Ford-Bellman sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.
• L'algorithme de Ford-Bellman nous permet de détecter un circuit absorbant. Dans ce cas, nous ne pouvons toutefois pas déterminer de chemin optimal.

Caractéristiques de l'algorithme de Ford-Bellman

Nous sommes à la recherche du chemin le plus court. Cela signifie que la somme des poids des arcs du chemin sélectionné doit être le plus faible possible.

L'algorithme de Ford-Bellman est différent des algorithmes que nous avons vu jusqu'à présent (Bellman-Kalaba, Moore-Dijkstra), qui nous permettaient une exploration progressive, sans back-tracking^[2].

Ford-Bellman remet en cause les résultats précédents car il accepte les circuits et les pondérations quelconques (alors que Moore-Dijkstra, s'il accepte les circuits, n'accepte pas de pondérations négatives).
La présence de pondérations négatives dans un graphe avec circuits ne permet plus de marquer définitivement un sommet, car le passage par un arc négatif décroît la valeur du chemin à chaque passage par ce circuit.

Principe de relâchement

Le principe général est le même que pour le relâchement dans Moore-Dijkstra : nous utiliserons une valeur tellement haute^[3] que tout au long de l'exécution de l'algorithme nous ne devrons jamais définir de nouvelles valeurs qui lui soient égales ou supérieures.

Nous diminuerons (relâcherons) cette valeur à chaque fois que nous trouverons une valeur plus intéressante.

Principe d'ajustement progressif

Les résultats ne sont pas définitifs, et sont remis en cause à chaque itération si un chemin plus court permet d'atteindre un sommet.

A chaque passage dans la boucle, nous devons trouver pour le sommet x les arcs incidents à x vers l'intérieur^[4], arcs (y -> x).

Nous calculons ensuite le coût (le poids) nécessaire pour atteindre x en passant par y. Ce coût (r -> y -> x) est calculé en ajoutant à la pondération de l'arc (y -> x), le poids du chemin de la racine vers y.

Si le poids minimum calculé pour x et tout y possible est inférieur à l'ancien poids (r -> x), nous devons remplacer ce poids par la nouvelle valeur, et mémoriser (par l'étiquette) que y est le meilleur précédent actuel pour atteindre x car nous vennons de découvrir un chemin plus court (de poids inférieur) de la racine vers x.

Code de l'algorithme de Ford-Bellman

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

Variables

Dans cette approche, nous utilisons des collections indexées (par exemple des tableaux) pour maintenir les différentes informations relatives aux états de chaque objet Sommet. Dans une approche "orienté-objet", nous pouvons maintenir ces informations par exemple dans l'objet Sommet lui même.

• verticesLabels est le tableau qui contient les étiquettes. L'étiquette d'un sommet x est l'indice du sommet y précédent de x dans le chemin optimum de la racine vers le sommet x.
• pathMinWeights est le tableau du coût (poids) des chemins depuis la racine jusqu'aux différents sommets.
  pathMinWeights[i] est le poids du chemin entre la racine et le sommet X[i].
• Alternatives :
  Version 1 :
  • pathTempWeights est le tableau qui contient les poids temporaires des chemins de la racine vers tout sommet. Nous devons ensuite vérifier pour chaque indice si le poids est inférieur au poids au même indice dans pathMinWeights.
  Version 2 :
  • pathTempWeight évite de calculer deux fois le poids du chemin.
  • modified est true si une amélioration est détectée et remet en cause les résultats (un nouveau passage dans la boucle est nécessaire).

Nous utiliserons aussi certaines variables supplémentaires :

• X est l'ensemble des sommets du graphe
• n est le nombre de sommets du graphe (la cardinalité de X).

arrayFirstIndex : indice du premier élément dans un tableau^[5].

Phase d'initialisation

• k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
• i := indice_de_la_racine // indice (dans X) du sommet racine (départ du chemin).
• Poids (r->x) :
  • pathMinWeights[i] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
  • ∀_(j ≠ i) pathMinWeights[j] := maxCost // Valeur hors des limites du possible^[3].
• Étiquettes :
  • ∀_(i > k) verticesLabels[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau^[6], même pour la racine car elle n'a pas de précédent.

Phase d'exécution

//Nombre maximum, sinon ∃ un circuit absorbant
tant_que k < n faire
 
	//pour tout sommet excepté la racine
	pour_tout x ;∈ ;X\{r} faire
 
		/*j est l'indice de y
		∃ y lié à x par un arc
		et le coût de y est ≤ au coût de tous les arcs*/
		si ∃ y ;: (y,x) ;∈ ;A ∧ pathMinWeights[j] ;&le; ;maxCost alors
 
			/*le poids temporaire de x est le minimum des poids
			des chemins pour atteindre x en passant par chaque y*/
			pathTempWeights[i] := minimum{(pathMinWeights[j]+weight(i,j))∀j};
 
			//poids plus court, amélioration
			si pathTempWeights[i] ;< ;pathMinWeights[i] alors
 
				//adaptation de l'étiquette
				verticesLabels[i] := j;
 
			fin si
 
		fin si
 
	fin pour_tout
 
	//si aucune amélioration n'a été détectée
	si ∀j ;: pathTempWeights[j]=pathMinWeights[j] alors
 
		//arrêt du programme
		afficher("fin de la recherche");
		fin_programme;
 
	sinon
 
		//si il reste des sommets à traiter
		si k ;<n alors
 
			//on diminue le nombre de passages restant
			k := k+1;
 
			/*des amélioration ont été détectées
			on met à jour le tableau des coûts*/
			pour_tout x ;∈ ;X\{r} faire
 
				pathMinWeights[i] := pathTempWeights[i];
 
			fin pour_tout
 
		sinon
 
			//arrêt du programme
			afficher("Détection de circuit absorbant");
			fin_programme;
 
fin tant_que
 
fin_programme;

Remarques

A la ligne 2, le test de comparaison k < n s'applique aux langages pour lesquels le premier indice d'un tableau est 0. Dans le cas où le premier indice est 1, nous devons remplacer le test par k ≤ n.

La condition ∧ pathMinWeights[j] ≤ maxCost n'est pas strictement nécessaire (car les mises à jour ne se font que lorsqu'une optimisation est détectée), mais elle permet d'éviter de prendre en compte inutilement certaines valeurs lors de la recherche de minimum.

Le pseudo code si ∃ y : (y,x) ∈ A ∧ pathMinWeights[j] ≤ maxCost alors correspond en réalité à un pour_tout car nous devons itérer tous les arcs candidats.

Pseudo codes alternatifs

//Nombre maximum, sinon ∃ un circuit absorbant
tant_que k < n faire
 
	//si modified=true, cela signifie qu'une optimisation a été détectée
	modified := false;
 
	//pour tout sommet excepté la racine
	pour_tout x ;∈ ;X\{r} faire
 
		//j est l'indice de y, précédent de x
		pour_tout y ;: (y,x) ;∈ ;A alors
 
			/*le poids pour atteindre x en passant par ce sommet y*/
			pathTempWeight := pathMinWeights[j]+weight(i,j);
 
			//poids plus court, amélioration
			si pathTempWeight ;< ;pathMinWeights[i] alors
 
				//mise à jour de la meilleur valeur
				pathMinWeights[i] := pathTempWeight;
 
				modified := true;//une amélioration est détectée
 
				//adaptation de l'étiquette
				verticesLabels[i] := j;
 
			fin si
		fin pour_tout
	fin pour_tout
 
	//Au moins une améliorationa été détectée
	si modified = true alors
 
		//on diminue le nombre de passages restant
		k := k+1;
 
	//Aucune amélioration n'a été détectée
	sinon
 
		//arrêt du programme
		afficher("fin de la recherche");
		fin_programme;
 
fin tant_que
 
/*Si un chemin avait été trouvé, le programme se
serait arêté avant ce point*/
afficher("Détection de circuit absorbant");
fin_programme;

Dans cette version, nous ne vérifions plus la valeur de k en cours d'itération. Si aucune amélioration n'est plus possible avant de sortir de la boucle principale, l'algorithme s'arrête de lui même.

Si nous arrivons au terme de la boucle principale sans quitter, c'est que nous sommes en présence d'un circuit absorbant.

Dans la version de base, nous devons parcourir tout le tableau des poids si ∀j : pathTempWeights[j]=pathMinWeights[j] alors, alors que nous sommes déjà dans une boucle, ce qui est très coûteux.

Une variable modified nous permet de détecter si les poids ont été mis à jour. Nous ne devons plus utiliser un tableau pathTempWeights, ni itérer ce dernier pour mettre à jour le tableau des poids. La variable modified sert donc de condition de sortie de l'algorithme, au méme titre que la boucle bornée de départ.

Pourquoi utiliser l'algorithme de Ford-Bellman

Lorsque nous ne connaissons pas précisément la destination, et que nous sommes en présence de circuits et de pondérations quelconques, nous operons pour l'algorithme de Ford-Bellman, car des circuits avec pondérations négatives risquent de former des circuits absorbants.

Si nous sommes en possession de plus d'informations, nous nous dirigerons vers un algorithme de type heuristique A*, qui limitera l'exploration à une direction qui correspond à la destination.

Exemples d'application de l'algorithme de Ford-Bellman

Une variante de Ford-Bellman est utilisée dans les protocoles de routage à vecteur-distance, comme par exemple RIP (Routing Information Protocol).

Notes

1. ↑ pondération : La pondération est une valeur associée à un arc (ou une arête), et correspond au coût du passage par cet arc. Par exemple, il peut s'agir d'une distance entre deux villes représentées chacune par un sommet du graphe.
   
   
2. ↑ retour en arrière : Les résultats stockés dans l'ensemble D sont acquis au fur et à mesure, et ne sont plus mis en doute par la suite.
   
   
3. ↑^a,b maxCost : La majorité des pseudo codes utilisent le symbole ∞ (infini) pour représenter une valeur hors des limites du possible, et dont les variations sont insignifiantes. JP Leclercq nous propose donc de travailler avec une valeur qui correspond à la somme des poids des arcs du graphe, car l'infini est une notion qui existe en mathématiques, mais qui ne correspond pas toujours à la réalité de la programmation. Nous utiliserons la notation maxCost, ou même 2maxCost dans les algorithmes pour lesquels cette valeur n'est pas suffisante.
   
   
4. ↑ Incidence : Les arcs incidents à x vers l'intérieur sont les arcs qui ont pour destination le sommet x.
   
   
5. ↑ arrayFirstIndex : Ce n'est pas à proprement parler une variable, mais cela me permet d'éviter d'écrire 0 ou 1 dans le pseudo-code de l'algorithme selon le type de langage utilisé.
   Selon l'implémentation choisie, la collection utilisée peut démarrer son indexation à 0 (ex : tableau en Java) ou à 1 (ex : tableau en Pascal). Par exemple, en Java nous initialisons avec ∀i : previousVertices[i] = 0
   
   
6. ↑ arrayFirstIndex-1 : Comme nous sélectionnons une valeur qui précède le premier indice du tableau, cela signifie que la valeur n'est pas encore significative.
   
   

Références

1. INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)
2. Bellman–Ford algorithm : Wikipedia (version 28/12/09)
3. Cours sur les graphes : les algorithmes : F. Madelaine, C. Simon, L'algorithme de Bellman-Ford et ses variantes (28/12/09)
4. Graph Theory Applet : Rensselaer Polytechnic Institute, Démonstration interactive par applet Java (version 28/12/09)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document