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 s0 qui est l'indice du sommet de départ.

On crée un tableau dist[s][k], où s est l'indice d'un sommet et k un entier. dist[s][k] représente la longueur du plus court chemin depuis s0 jusqu'à s et n'utilisant, au plus, 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[s0][0] = 0
• dist[s][0] = float('inf') pour s != s0

• Pour chaque k dans 1, 2, …
  • pour chaque s, on calcule les dist[s][k].

On utilise la règle suivante : dist[s][k] est la plus petite valeur entre

• dist[s][k-1],
• le minimum des dist[si][k-1] + poids(si,s) où si est un antécédent de s et poids(si,s) est la pondération de l'arc si → 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 sf, il faut renvoyer dist[sf][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 un autre tableau 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

On peut procéder ainsi (exemple d'un trajet R1 → ?

• on initialise le tableau (ou dictionnaire) dist.
  par exemple ''%%dist = {“R