Plus courts chemins : Dijkstra et au-delà

14.1 Introduction et motivation

« Itinéraire le plus rapide vers… » : la phrase la plus tapée des applications de navigation est une question de graphe pondéré — et la réponse, calculée en quelques millisecondes sur un réseau routier de plusieurs millions de carrefours, sort d'un algorithme conçu en 1956 par Edsger Dijkstra, en vingt minutes dit-il, à la terrasse d'un café d'Amsterdam. Le chapitre 13 savait minimiser le nombre d'étapes (parcours en largeur) ; dès que les arcs portent des poids — kilomètres, minutes, coûts — ce n'est plus la bonne réponse : deux petites étapes valent mieux qu'une grande, et il faut un algorithme qui additionne les poids.

L'algorithme de Dijkstra est ce qu'il faut : une généralisation du parcours en largeur où la file d'attente ne sert plus les sommets par ancienneté mais par distance provisoire croissante — une file de priorité, qu'on implémentera naïvement comme le permet le programme. Sa correction repose sur un invariant d'une élégance rare, et sur une hypothèse à ne jamais oublier : les poids sont positifs. Le chapitre s'achève sur une ouverture : l'algorithme A, variante de Dijkstra guidée par une heuristique* — l'idée qui fait passer de « explorer en rond » à « viser la cible », et la première rencontre du cours avec une notion qui irrigue toute l'intelligence artificielle.

14.2 Le problème, et pourquoi le BFS ne suffit plus

Exemple 14.2Le BFS se trompe dès que les poids parlent

Le parcours en largeur répond « $s\to t$ directement » ($1$ étape) ; mais ce chemin pèse $10$, quand $s\to a\to t$ pèse $2$. Compter les arcs et additionner les poids sont deux problèmes distincts — le BFS résout le premier, Dijkstra le second (et les confond exactement quand tous les poids valent $1$ : le BFS est le cas particulier).

14.3 L'algorithme de Dijkstra

14.3.1 L'idée : figer les sommets par distance croissante

L'algorithme entretient pour chaque sommet une distance provisoire — le poids du meilleur chemin connu jusqu'ici — et fige les sommets un par un : à chaque tour, le sommet non figé de plus petite distance provisoire est promu définitif (on prouvera que sa provisoire est alors exacte), et ses voisins voient leur provisoire s'améliorer s'il offre un raccourci. C'est une stratégie gloutonne (chapitre 7 !) — et, pour une fois, prouvablement optimale.

def dijkstra(R: dict, source) -> tuple:
    """R : graphe pondéré {u: {v: poids}}, poids > 0.
    Renvoie (dist, pere) : distances exactes depuis source, et l'arbre
    des pères pour reconstruire les chemins."""
    dist = {s: float("inf") for s in R}
    dist[source] = 0
    pere = {}
    a_traiter = set(R)                       # les sommets non encore figés
    while a_traiter:
        # EXTRACTION DU MINIMUM (file de priorité naïve : un parcours)
        s = None
        for x in a_traiter:
            if s is None or dist[x] < dist[s]:
                s = x
        if dist[s] == float("inf"):
            break                            # le reste est inaccessible
        a_traiter.remove(s)                  # s est FIGÉ : dist[s] est exacte
        # RELÂCHEMENT des arcs sortants de s (vers les sommets non figés)
        for v in R[s]:
            if v in a_traiter and dist[s] + R[s][v] < dist[v]:
                dist[v] = dist[s] + R[s][v]  # un raccourci via s !
                pere[v] = s
    return (dist, pere)