06 — Dijkstra : le plus court chemin pondéré

Ce que tu vas apprendre

• Pourquoi BFS ne suffit plus quand les arêtes ont des poids
• Le principe glouton de Dijkstra
• L'implémentation avec une file de priorité
• Sa complexité et sa limite stricte : pas de poids négatifs

Prérequis

• 02 — Le parcours en largeur (BFS)
• La file de priorité de la série Structures de données

BFS trouve le chemin avec le moins d'arêtes, mais le monde réel a des poids : une route plus longue qu'une autre, une connexion plus lente, un coût plus élevé. Le chemin avec le moins d'étapes n'est alors pas forcément le moins coûteux. L'algorithme de Dijkstra, publié en 1959, résout ce problème : il trouve le plus court chemin pondéré depuis une source, à condition que les poids soient positifs. C'est le moteur derrière le calcul d'itinéraire GPS et le routage réseau.

L'idée gloutonne

Dijkstra maintient, pour chaque sommet, la plus courte distance connue depuis la source, initialisée à l'infini sauf pour la source (à zéro). Il répète une étape gloutonne : parmi les sommets pas encore finalisés, prendre celui de plus petite distance connue, le finaliser, et mettre à jour ses voisins.

La mise à jour s'appelle la relaxation : si passer par le sommet courant offre un chemin plus court vers un voisin que ce qu'on connaissait, on améliore la distance de ce voisin.

L'invariant qui rend l'algorithme correct : quand on finalise un sommet (celui de plus petite distance), sa distance est définitive. Aucun chemin futur ne pourra faire mieux, parce que tous les autres chemins passeraient par des sommets de distance déjà supérieure, et les poids étant positifs, ils ne feraient qu'augmenter. C'est précisément cet argument qui s'effondre avec des poids négatifs.

L'implémentation avec file de priorité

Pour choisir efficacement le sommet de plus petite distance à chaque étape, on utilise une file de priorité (min-heap, série Structures de données). Sans elle, chercher ce minimum coûterait O(V) à chaque tour, et l'algorithme serait en O(V²).

pythonimport heapq

def dijkstra(graphe, source):
    # graphe[u] = liste de (voisin, poids)
    distances = {s: float("inf") for s in graphe}
    distances[source] = 0
    file = [(0, source)]          # (distance, sommet)
    while file:
        dist, u = heapq.heappop(file)   # sommet de plus petite distance
        if dist > distances[u]:
            continue                    # entrée périmée, on l'ignore
        for voisin, poids in graphe[u]:
            nouvelle = dist + poids
            if nouvelle < distances[voisin]:   # relaxation
                distances[voisin] = nouvelle
                heapq.heappush(file, (nouvelle, voisin))
    return distances

Le test if dist > distances[u]: continue mérite une explication. La file peut contenir d'anciennes entrées pour un sommet dont on a déjà trouvé un meilleur chemin depuis. Plutôt que de les supprimer (coûteux dans un tas), on les laisse et on les ignore au moment où on les défile. C'est une astuce d'implémentation standard et propre.

Pour reconstruire le chemin, et pas seulement les distances, on mémorise le prédécesseur de chaque sommet à chaque relaxation, comme pour BFS.

La complexité

Chaque arête peut provoquer un ajout dans la file (O(log V)), et chaque sommet est défilé. Avec une file de priorité binaire, la complexité est O((V + E) log V). C'est excellent pour les graphes creux, qui sont la norme. Une file de priorité plus sophistiquée (tas de Fibonacci) abaisse la borne théorique à O(E + V log V), mais en pratique le tas binaire suffit et est plus simple.

La limite : pas de poids négatifs

Dijkstra est faux si une arête a un poids négatif. La raison est l'invariant glouton : Dijkstra finalise un sommet en supposant qu'aucun chemin futur ne pourra l'améliorer. Avec une arête négative, un chemin plus long en sommets pourrait pourtant coûter moins cher, en empruntant cette arête négative plus tard. Dijkstra aurait déjà finalisé le sommet à tort.

Ce n'est pas une faiblesse d'implémentation, c'est une limite de l'algorithme. Quand les poids peuvent être négatifs (un graphe où certaines arêtes représentent un gain, un remboursement, une réduction), il faut un autre algorithme, Bellman-Ford, sujet de l'article suivant. Bellman-Ford gère les poids négatifs et détecte même les cycles de poids négatif, au prix d'une complexité plus élevée.

L'article suivant présente Bellman-Ford pour les poids négatifs, et A*, une amélioration de Dijkstra guidée par une heuristique, très utilisée dans les jeux et la navigation.

Sources

• Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1. (Article original)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 24.3 "Dijkstra's Algorithm". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.4 "Shortest Paths". Addison-Wesley.