No cache version.

Caching disabled. Default setting for this page:enabled (code LNG204)
If the display is too slow, you can disable the user mode to view the cached version.

Exemple d'algorithme de Bellman-Kalaba

Légende & situation

Le tableau de départ contient les sommets suivants :

  • "Sommet 2" à l'indice 0.
  • "Sommet 4" à l'indice 1.
  • "Sommet 6" à l'indice 2.
  • "Sommet 5" à l'indice 3.
  • "Sommet 1" à l'indice 4.
  • "Sommet 3" à l'indice 5.
Bellman-Kalaba, légende

[Étape 0-0]  Initialisation des valeurs

Bellman-Kalaba, image 0-0

Les variables utilisées ici les mêmes que lors des explications sur l'algorithme Bellman-Kalaba, sauf pour le tableau definedVertices qui est réduit dans les images à la lettre D :

  • k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
  • 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.
  • pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
  • verticesLabels[definedVertices[k]] := arrayFirstIndex]-1 // Étiquette de la racine. Pointe vers un emplacement non valide car la racine n'a pas de précédent.

Recherche du 1e sommet pour le chemin optimum

[Étape 1-0]  Rejet du sommet 3

Bellman-Kalaba, image 1-0

Les sommets candidats au chemin optimum sont {2,3}. Nous ne pouvons sélectionner le sommet 3 car le sommet 2 précédent de 3 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 2.

i := choisir x ∈ {3 | (3 ∈ X\definedVertices)(Γ-1(3) ⊂ definedVertices ≠ ∅)};

Contents Haut

[Étape 1-1]  Sélection du sommet 2

Bellman-Kalaba, image 1-1

definedVertices[k] := i; devient definedVertices[0] := 0; et X[0] = sommet 2.

Le sommet 2 est sélectionné pour le chemin optimum.

Recherche du 2e sommet pour le chemin optimum

[Étape 2-0]  Rejet du sommet 4

Bellman-Kalaba, image 2-0

Les sommets candidats au chemin optimum sont {4,3}. Nous ne pouvons sélectionner le sommet 4 car le sommet 3 précédent de 4 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 3.

i := choisir x ∈ {4 | (4 ∈ X\definedVertices)(Γ-1(4) ⊂ definedVertices ≠ ∅)};

Contents Haut

[Étape 2-1]  Sélection du sommet 3

Bellman-Kalaba, image 2-1

definedVertices[k] := i; devient definedVertices[0] := 5; et X[5] = sommet 3.

Le sommet 3 est sélectionné pour le chemin optimum.

Recherche du 3e sommet pour le chemin optimum

[Étape 3-0]  Rejet du sommet 6

Bellman-Kalaba, image 3-0

Les sommets candidats au chemin optimum sont {4,5,6}. Nous ne pouvons sélectionner le sommet 6 car le sommet 5 précédent de 6 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 5.

i := choisir x ∈ {6 | (6 ∈ X\definedVertices)(Γ-1(6) ⊂ definedVertices ≠ ∅)};

[Étape 3-1]  Recherche du minimum entre {4 (avec un poids de 6),5 (avec un poids de 9)}

Bellman-Kalaba, image 3-1

Les sommets candidats au chemin optimum sont {4 (avec un poids de 6),5 (avec un poids de 9)} Nous devons sélectionner le sommet 4 car il possède le poids le moins élevé (6) parmi les candidats.

pathMinWeights[i] := minimum{ pathMinWeigths[j]+weight(j,i)∀j∈&Gamma-1(x)};

Contents Haut

[Étape 3-2]  Sélection du sommet 4

Bellman-Kalaba, image 3-2

definedVertices[k] := i; devient definedVertices[0] := 1; et X[1] = sommet 4.

Le sommet 4 est sélectionné pour le chemin optimum.

Recherche du 4e sommet pour le chemin optimum

[Étape 4-0]  Rejet du sommet 6

Bellman-Kalaba, image 4-0

Les sommets candidats au chemin optimum sont {5,6}. Nous ne pouvons sélectionner le sommet 6 car le sommet 5 précédent de 6 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 5.

i := choisir x ∈ {6 | (6 ∈ X\definedVertices)(Γ-1(6) ⊂ definedVertices ≠ ∅)};

Contents Haut

[Étape 4-1]  Sélection du sommet 5

Bellman-Kalaba, image 4-1

definedVertices[k] := i; devient definedVertices[0] := 3; et X[3] = sommet 5.

Le sommet 5 est sélectionné pour le chemin optimum.

Contents Haut

Dernier sommet pour le chemin optimum (arrivée)

[Étape 5-0]  Sélection du sommet 6

Bellman-Kalaba, image 5-0

definedVertices[k] := i; devient definedVertices[0] := 2; et X[2] = sommet 6.

Le sommet 6 est sélectionné pour le chemin optimum.

Chemin optimum trouvé par l'algorithme de Bellman-Kalaba

Graphes : Bellman-Kalaba chemin optimumError Infobrol

Can not display this page of the Infobrol website

Type of error (18-01)

Unknown format specifier "&"

Please try again in a few minutes…

Return to the home page




Steph