#Plus courts chemins (Dijkstra)Copier le lien

Objectifs d'apprentissage

• Comprendre la relaxation d'arc et l'invariant d'exploration par distances croissantes.
• Implémenter la version file de priorité avec entrées périmées, et reconstruire un chemin via les prédécesseurs.
• Identifier les limites : poids négatifs, graphes denses, variantes multi-sources.

Prérequis : files de priorité (tas) du parcours L2 ; BFS (chapitre Parcours de graphes) ; notation O.

#PrincipeCopier le lien

L'algorithme maintient une distance provisoire dist[u] pour chaque sommet, initialisée à l'infini sauf pour la source (zéro). Une file de priorité ordonne les sommets par distance croissante. À chaque itération, on extrait le sommet de plus petite distance et on tente d'améliorer (« relâcher ») ses voisins : si dist[u] + poids(u, v) < dist[v], on met à jour dist[v] et on réinsère v dans la file. On répète jusqu'à vider la file ; si l'on ne cherche qu'une cible t, on peut s'arrêter dès que t est extrait : sa distance est alors définitive.

Pourquoi c'est correct (invariant) : au moment où un sommet u est extrait, dist[u] est sa distance minimale. Supposons le contraire : un chemin plus court passerait par un premier sommet x non encore fixé, extrait avant u dans le pire des ordres. Comme tous les poids sont non négatifs, la portion de chemin jusqu'à x coûte au moins dist[x], donc ce chemin ne peut pas être plus court que dist[u] : contradiction. C'est exactement ici que la preuve casse avec des poids négatifs.

#Visualisation interactiveCopier le lien

Entrées : un graphe pondéré (poids non négatifs) et un sommet source. Sorties : l'ordre de figement des sommets et la distance définitive de chacun. Repère visuel : les sommets prennent leur couleur définitive au moment de leur extraction, jamais après ; tout sommet revenu en arrière signalerait une erreur d'implémentation.

#Animation : déroulé conceptuelCopier le lien

#Implémentation (Python)Copier le lien

1import heapq2 3def dijkstra(graphe, source):4    """graph : dict sommet -> dict voisin -> poids (poids >= 0).5    Renvoie (distances, predecesseurs)."""6    INF = float('inf')7    dist = {s: INF for s in graphe}8    prev = {s: None for s in graphe}9    dist[source] = 010    file = [(0, source)]11 12    while file:13        d, u = heapq.heappop(file)14        if d != dist[u]:

Deux choix d'implémentation à retenir :

• Entrées périmées : plutôt que de décrémenter une clé dans le tas (coûteux), on insère la nouvelle distance et on ignore à l'extraction toute entrée dont la distance ne correspond plus à dist[u]. La file peut contenir plusieurs fois le même sommet ; c'est sans conséquence.
• Prédécesseurs : reconstruire le chemin après coup en O(longueur du chemin), sans stocker les listes de sommets à chaque mise à jour (ce qui coûterait O(E × V) en mémoire dans le pire cas).

#ComplexitéCopier le lien

Chaque relâchement réussi insère une entrée dans le tas : au plus E insertions et E extractions, chacune en O(log E) = O(log V) sur un graphe simple. Avec un tas binaire, la complexité totale est O((V + E) log V). Sur un graphe dense (E proche de V²), la variante sans tas (recherche linéaire du minimum parmi les non fixés) donne O(V²), souvent plus rapide en pratique car sans coût de tas. Un tas de Fibonacci abaisserait la borne théorique à O(E + V log V), mais ses constantes le rendent rarement rentable en pratique.

#Pièges et variantesCopier le lien

• Multi-sources : initialiser la file avec toutes les sources à distance 0 ; utile pour « distance au poste le plus proche ».
• Graphe dense : préférer la variante O(V²) à tableau, sans tas.
• Orienté ou non : sur un graphe non orienté, chaque arête apparaît dans les deux listes d'adjacence ; oublier la symétrie donne des distances fausses, la doubler par erreur double le travail.
• Cible unique : s'arrêter à l'extraction de t (pas à sa mise à jour) ; avant l'extraction, dist[t] peut encore baisser.
• Reconstruction en boucle : sur un graphe mal formé, la remontée des prédécesseurs peut cycler ; borne le nombre d'étapes à V-1 pour détecter l'anomalie.

#Exercices avec vérificationCopier le lien

1. Ajoutez l'arête 'B' -> 'D' de poids 2 au graphe d'exemple et vérifiez que chemin(prev, 'D') vaut ['A', 'B', 'D'] pour un coût de 3.
2. Remplacez le tas par une recherche linéaire du minimum (liste des sommets non fixés) et comparez les temps sur un graphe aléatoire de 2000 sommets dense puis clairsemé ; observez où la variante O(V²) reprend l'avantage.
3. Écrivez la version multi-sources et vérifiez sur un petit graphe que chaque sommet reçoit la distance à la source la plus proche.

#Mini-quizCopier le lien