Algorithme de Ford-Bellman

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³ 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⁴, 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.

Table des matières Haut

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⁵.

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³.
• Étiquettes :
  • ∀_(i > k) verticesLabels[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau⁶, 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.