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 voudrait obtenir une table de routage pour l'ensemble du graphe.

Cette table aurait la forme suivante :

• table[s1][s2] est un tableau (ou dictionnaire),
• s1 est un sommet de départ et s2 un sommet d'arrivée,
• table[s1][s2] contient une paire formée de :
  • le sommet vers lequel s1 doit envoyer ses messages à destination de s2
  • la distance correspondante

On peut initialiser le tableau table en mettant la paire table[s][s] = (s, 0) pour tous les sommets s du graphe.

On met en place aussi une file changements qui indique les routes qui ont subit un changement. changements contient des paires (s1, s2). Une telle paire signifie que s1 a vu s'améliorer sa route pour s2.

On initialise changements en y plaçant des paires (s,s) pour tous les sommets.

Enfin on lance une boucle : Tant que changements n'est pas vide :

• on défile la prochaine paire (s1,s2)
• on parcours tous les voisins v de s1 :
  • si cett
• on parcours tous les voisins v de s et pour chacun :
  • on calcule

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

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