Fiche Wikipedia

Comme l'algorithme de Dijkstra, il s'agit d'une recherche de plus court chemin dans un graphe.

À titre d'exemple, nous considérerons le graphe suivant :

On considère un sommet $s_0$ qui est le sommet de départ.

On crée un tableau $dist(s, k)$, où $s$ est un sommet et $k$ un entier. $dist(s, k)$ représente la longueur du plus court chemin depuis $s_0$ jusqu'à $s$ et n'utilisant que $k$ arêtes.

Si on ne s'autorise aucune arête, seul le point de départ peut être atteint, à coût nul. Les autres sont inatteignables.

• $dist(s_0, 0) = 0$
• $dist(s, 0) = \infty$ pour $s \neq s_0$

On itère sur $k$ : $k$ parcours les valeurs 1, 2, … Et pour chaque valeur de $k$, on calcule les $dist(s, k)$ pour tous les sommets.

On utilise la règle suivante : $dist(s,k)$ est la plus petite valeur entre

• $dist(s, k-1)$,
• le minimum des $dist(s',k-1) + poids(s',s)$ où $s'$ est un antécédent de $s$ et $poids(s',s)$ est la pondération de l'arc $s' \to s$.

Dans un graphe d'ordre $n$, si on ne fait pas de boucles, un chemin parcourt au plus $n$ sommets. Un parcours de $n$ sommets nécessite le passage de $n-1$ arêtes.

On peut donc arrêter l'itération sur $k$ quand $k = n-1$.

Si le sommet final demandé est $s_f$, il faut renvoyer $dist(s_f, n-1)$.

Dans ce qui précède, nous avons considéré que $dist(s, k)$ ne contient que la longueur d'un chemin. On peut si on le souhaite demander que $dist(s,k)$ contienne également la liste des sommets à visiter pour ce chemin. On peut aussi construire $chemin(s,k)$ pour stocker ces chemins.

Envisageons le chemin R1 – R7

• De la ligne $k = 4$ à la ligne $k = 5$, il n'y a pas de changement. On pourrait s'arrêter là.
• Observons à titre d'exemple le calcul pour R6. En ligne $k = 2$, on avait 3 comme meilleure distance pour R4. Cela nous donnait en ligne $k = 3$ un meilleure distance de 6 pour R6.
  Mais en ligne $k = 3$, la meilleure distance pour R4 passe à 2. Cela permet une amélioration, en ligne $k = 4$, de la meilleure distance pour R6.
• Il suffit d'observer les colonnes qui changent. Par exemple, si la colonne R3 change, il faut consulter les colonnes R5 et R1 pour voir si elles ne changeront pas non plus.1