Algorithme de Bellman-Kalaba

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).
• k est le compteur utilisé pour trouver le prochain emplacement libre dans le tableau definedVertices.
• i est l'indice dans X du sommet en cours d'évaluation.

arrayFirstIndex : indice du premier élément dans un tableau⁵.

Phase d'initialisation

Nous devons initialiser les tableaux avec une taille correspondant à n.

Nous emploierons ∀j pour raccourcir la notation ∀_{(j ≥ arrayFirstIndex) ∧ (j < n+arrayFirstIndex)}, ce qui signifie pour tout emplacement du tableau.

• k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
• Sommets traités :
  • definedVertices[k] := indice_de_la_racine //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 :
  • pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
  • ∀_(i > k) pathMinWeights[i] := ?⁷ //.
• É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
	x est non traité mais tous ses précédents le sont*/
	i := choisir x ∈ {y |&thinsp;(y ∈ X\definedVertices) ∧ (&Gamma;<sup>-1</sup>(y) &sub; definedVertices &ne; &empty;)};
 
	//trouver le coût minimum
	pathMinWeights[i] := minimum{ pathMinWeigths[j]+weight(j,i)∀j∈&Gamma<sup>-1</sup>(x)};
 
	//j est l'indice du sommet qui a satisfait le test du minimum
	verticesLabels[i] := j;
 
	k := k+1;
 
	//i est défini comme ∈ au chemin de poids minimum
	definedVertices[k] := i;
 
fin tant_que

/* ∃ j précédent de i
i est l'indice de x dans X*/
tant_que ∃ j : (i,j) ∈ &Gamma<sup>-1</sup>(i)
 
	//on évite de faire calcul plusieurs fois
	temp := pathMinWeights[j] + weight(j,i);
 
	//le résultat est meilleur
	si temp < tempMin alors
 
		//mémoriser comme meilleur candidat au minimum
		tempMin := temp;
		//indice du sommet meilleur candidat
		tempVertrex := j;
 
	fin si
 
fin tant_que
pathMinWeights[i] :=  pathMinWeigths[j]+weight(j,i);
verticesLabels[i] := i;