Principe de relâchement

Nous allons fixer 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.

Le principe de relâchement nous permet d'utiliser cette borne supérieure sur le poids du plus court chemin, et de diminuer progressivement cette borne.

A chaque étape, nous devons choisir le sommet x à traiter parmi les sommets non encore traités, avec le chemin de poids le plus faible depuis le sommet précédent (x->y).
Il s'agit d'un choix glouton⁶, qui dans ce cas se révèle optimal.

Nous retirons ensuite x des sommets à traiter (en ajoutant son indice dans definedVertices).

Nous devons maintenant consulter les poids de x vers tout sommet non traité.
Pour tous les sommets non traités restants, nous comparons le poids du chemin (r->x->y) entre la racine r et ce sommet y en passant par x.

Si le poids du nouveau chemin est inférieur au poids précédent (dans pathMinWeights), il est retenu comme meilleur chemin, et la valeur de pathMinWeights est remplacée par ce meilleur chemin, et donc diminuée (relâchement).

Contents 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].
• definedVertices est le tableau qui contient les sommets traités (définis comme ∈ au chemin à renvoyer).

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.
• j := indice_de_la_racine // indice (dans X) du sommet racine (départ du chemin).
• Sommets traités :
  • definedVertices[k] := j //la racine fait d'office partie du chemin, car elle est le point de départ⁴. Nous pouvons donc stocker au premier emplacement de definedVertices l'indice (dans X) du sommet de départ.
  • ∀_(i > k) : definedVertices[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau⁸.
• Poids (r->x) :
  • pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
  • ∀_(i > k) pathMinWeights[i] := 2maxCost // Valeur hors des limites du possible (double de maxCost⁵).
• Étiquettes :
  • verticesLabels[definedVertices[k]] := arrayFirstIndex // Étiquette de la racine. Pointe vers un emplacement non valide car la racine n'a pas de précédent.
  • ∀_(i > k) verticesLabels[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau⁸.

Phase d'exécution

//Il reste des sommets non traités
tant_que k < n faire
 
	/*i est l'indice de x, j est l'indice de y
	x est non traité, et le chemin(r,x) est le plus court
	de tous les chemins de r vers un sommet non traité */
	i := choisir x ∈ {y |&thinsp;(y ∈ X\definedVertices) ∧
		(pathMinWeights[i]=minimum{pathMinWeights[j]∀j∈ X\definedVertices})};
 
	//k pointe à présent sur le prochain emplacement libre de definedVertices
	k := k+1;
 
	//i est défini comme étant traité
	definedVertices[k] := i;
 
	//vérifier si ce chemin est le meilleur
	pour_tout y ∈ X\definedVertices faire
 
		/*si x est un précédent de y sur un chemin
		plus court que le meilleur chemin actuel...*/
		si pathMinWeights[i]+weight(i,j) < pathMinWeights[j] alors
 
			//le poids du chemin vers "y" est mis à jour
			pathMinWeights[j] := pathMinWeights[i]+weight(i,j);
 
			//j est l'indice du sommet précédent de "x"
			verticesLabels[i] := j;
 
		fin si
	fin pour_tout
fin tant_que

//vérifier si ce chemin est le meilleur
pour_tout y ∈ X\definedVertices faire
 
	tempWeight := memo(pathMinWeights[i]+weight(i,j));
 
	/*si x est un précédent de y sur un chemin
	plus court que le meilleur chemin actuel...*/
	si tempWeight < pathMinWeights[j] alors
 
		//le poids du chemin vers "y" est mis à jour
		pathMinWeights[j] := tempWeight;
 
		//j est l'indice du sommet précédent de "x"
		verticesLabels[i] := j;
 
	fin si
fin pour_tout