Algorithme de Dijkstra : le plus court chemin pas à pas

L'algorithme de Dijkstra calcule, dans un graphe valué dont toutes les valeurs sont positives ou nulles, les chemins de valeur minimale depuis un sommet de départ vers tous les autres sommets, même si le graphe a des circuits. À chaque étape, il fixe définitivement le sommet le plus proche du départ parmi ceux qui ne sont pas encore fixés, puis met à jour les distances provisoires de ses successeurs. Ce chapitre détaille l'algorithme, la présentation en tableau attendue sur une copie, la reconstruction du chemin, ses limites, et son usage dans le routage OSPF.

Le principe

Edsger Dijkstra, informaticien néerlandais, a conçu cet algorithme en 1956 et l'a publié en 1959. L'idée repose sur le principe d'optimalité du chapitre 6 : le plus court chemin vers un sommet passe par des plus courts chemins vers les sommets intermédiaires.

L'algorithme donne à chaque sommet une marque : la valeur du meilleur chemin trouvé jusqu'ici depuis le départ, et le sommet d'où l'on vient. Au début, le départ a la marque 0 et tous les autres la marque ∞ (aucun chemin connu). Puis on répète :

1. parmi les sommets non fixés, on choisit celui qui a la plus petite marque et on le fixe : sa marque est définitive ;
2. pour chaque successeur y non fixé de ce sommet x, on calcule marque(x) + v(x, y) ; si c'est plus petit que la marque actuelle de y, on la remplace, et on note que y vient de x.

On s'arrête quand tous les sommets atteignables sont fixés (ou dès que le sommet d'arrivée est fixé, si seul lui nous intéresse).

Exemple de l'algorithme de Dijkstra pas à pas

Six routeurs A, B, C, D, E, F sont reliés par des liens orientés ; la valeur d'un arc est le coût du lien (plus il est petit, plus le lien est rapide). Le graphe a des circuits (A → B → A, C → D → C…), on ne peut donc pas utiliser la méthode par niveaux.

On cherche les chemins de coût minimal depuis A.

Le tableau. Chaque ligne donne les marques après la mise à jour faite depuis le sommet fixé à la ligne précédente. « 5 (C) » se lit : marque 5, on vient de C. Le sommet fixé de chaque ligne est en gras ; une fois fixé, un sommet n'apparaît plus.

Le raisonnement, ligne par ligne :

• Départ. A a la marque 0, les autres ∞. On fixe A.
• Étape 1. Successeurs de A : B reçoit 0 + 7 = 7, C reçoit 0 + 2 = 2. La plus petite marque non fixée est 2 : on fixe C.
• Étape 2. Successeurs de C : B, 2 + 3 = 5, mieux que 7, on remplace par 5 (C) ; D, 2 + 8 = 10 ; E, 2 + 5 = 7. On fixe B (5).
• Étape 3. Successeurs de B : A est fixé, on l'ignore ; D, 5 + 4 = 9, mieux que 10, on remplace par 9 (B). Les marques non fixées sont D : 9, E : 7, F : ∞. On fixe E (7).
• Étape 4. Successeurs de E : D, 7 + 1 = 8, mieux que 9, on remplace par 8 (E) ; F, 7 + 9 = 16. On fixe D (8).
• Étape 5. Successeurs de D : C est fixé ; F, 8 + 3 = 11, mieux que 16, on remplace par 11 (D). On fixe F (11). Tous les sommets sont fixés.

Reconstruire un chemin. On part de l'arrivée et on remonte les « vient de » : F vient de D, D de E, E de C, C de A. Le chemin de coût minimal de A vers F est (A, C, E, D, F), de coût 2 + 5 + 1 + 3 = 11.

De la même façon : vers B, (A, C, B), coût 5 ; vers D, (A, C, E, D), coût 8 ; vers E, (A, C, E), coût 7. Le lien direct A → B (7) est moins intéressant que le détour par C (5) : c'est tout l'intérêt de l'algorithme.

Pourquoi ça marche, et quand ça ne marche pas

Quand on fixe le sommet x de plus petite marque m, tout autre chemin vers x devrait passer par un sommet non fixé, dont la marque est déjà au moins m ; comme les valeurs des arcs sont positives ou nulles, la suite du chemin ne peut que l'allonger. Aucun chemin ne peut donc faire mieux que m : la marque est définitive.

Ce raisonnement tombe si un arc a une valeur négative. Exemple : arcs A → B (2), A → C (3), C → B (−2). Dijkstra fixe B avec la marque 2 dès la deuxième étape, alors que le chemin (A, C, B) vaut 3 − 2 = 1. L'algorithme rend un résultat faux. Les valeurs négatives (un gain plutôt qu'un coût) demandent d'autres algorithmes, comme celui de Bellman-Ford, hors programme.

Dijkstra dans les réseaux : le routage OSPF

Le protocole de routage dynamique OSPF (Open Shortest Path First), utilisé dans les réseaux d'entreprise, fonctionne exactement ainsi. Chaque routeur connaît, grâce aux annonces de ses voisins, la carte complète de la zone : un graphe dont les sommets sont les routeurs et les réseaux, et dont les arcs ont un coût lié au débit des liens. Chaque routeur lance l'algorithme de Dijkstra depuis lui-même (le nom « shortest path first » désigne cet algorithme) et en déduit, pour chaque destination, le premier saut à emprunter : c'est sa table de routage. Quand un lien tombe, la carte change et chaque routeur relance le calcul. Le fonctionnement des routeurs et des tables de routage est détaillé dans le cours routage et commutation.

Lire une table de routage dans le tableau. Pour le routeur A de l'exemple, le premier saut vers chaque destination se lit en remontant le chemin jusqu'au sommet qui suit A : vers B, C, D, E et F, le premier saut est toujours C. Tout le trafic de A passe par le lien A → C, ce qui montre aussi son importance : s'il tombe, OSPF recalcule et le trafic vers B passera par le lien direct A → B.

En Python

def dijkstra(graphe, depart):
    """graphe : dict sommet -> dict successeur -> valeur (valeurs >= 0).
    Renvoie (marques, vient_de)."""
    INFINI = float("inf")
    marque = {x: INFINI for x in graphe}
    vient_de = {x: None for x in graphe}
    marque[depart] = 0
    fixes = set()
    while len(fixes) < len(graphe):
        # sommet non fixé de plus petite marque
        candidats = [x for x in graphe if x not in fixes and marque[x] < INFINI]
        if not candidats:
            break                       # les sommets restants sont inaccessibles
        x = min(candidats, key=lambda s: marque[s])
        fixes.add(x)
        for y, v in graphe[x].items():
            if y not in fixes and marque[x] + v < marque[y]:
                marque[y] = marque[x] + v
                vient_de[y] = x
    return marque, vient_de

def chemin(vient_de, arrivee):
    """Remonte les « vient de » depuis l'arrivée."""
    c = [arrivee]
    while vient_de[c[0]] is not None:
        c.insert(0, vient_de[c[0]])
    return c

reseau = {"A": {"B": 7, "C": 2}, "B": {"A": 7, "D": 4},
          "C": {"B": 3, "D": 8, "E": 5}, "D": {"C": 2, "F": 3},
          "E": {"D": 1, "F": 9}, "F": {}}
marque, vient_de = dijkstra(reseau, "A")
print(marque)                   # {'A': 0, 'B': 5, 'C': 2, 'D': 8, 'E': 7, 'F': 11}
print(chemin(vient_de, "F"))    # ['A', 'C', 'E', 'D', 'F']

Cette version cherche le minimum en parcourant tous les sommets à chaque étape, ce qui suffit pour des graphes de quelques centaines de sommets. Les routeurs et les GPS utilisent une file de priorité (un tas, module heapq en Python) pour trouver le minimum plus vite.

Exercices