Plus courts chemins (Dijkstra)

#Plus courts chemins — DijkstraCopier le lien

Objectifs d’apprentissage

• Comprendre la relaxation, l’invariant de l’exploration par distances croissantes.
• Utiliser une file de priorité et éviter les mises à jour coûteuses (technique des entrées « outdated »).
• Identifier les limites: poids négatifs, graphes denses, variantes multi‑sources.

#PrincipeCopier le lien

L’algorithme maintient une distance minimale dist[u] pour chaque sommet, initialisée à l’infini sauf pour la source. Une file de priorité ordonne les sommets par coût croissant. À chaque itération, on extrait le sommet de coût minimal et on tente d’améliorer (« relaxer ») ses voisins. Le procédé se répète jusqu’à explorer tous les sommets atteignables; si l’on cherche uniquement un but t, on peut s’arrêter dès que t est extrait de la file: sa distance est alors optimale.

#Visualisation interactiveCopier le lien

#Animation: déroulé conceptuelCopier le lien

#Implémentation (Python)Copier le lien

1import heapq2 3def dijkstra(graph, start):4    # graph: dict[str, dict[str, int]]  ex: {'A': {'B':1,'C':4}, 'B': {'C':2}}5    INF = 10**186    dist = {u: INF for u in graph}7    prev = {u: None for u in graph}8    dist[start] = 09    pq = [(0, start)]10 11    while pq:12        d, u = heapq.heappop(pq)13        if d != dist[u]:14            continue

#ComplexitéCopier le lien

Avec un tas binaire, la complexité est O((V+E) log V). Sur graphe dense, une variante sans tas donne O(V^2) et reste acceptable. En théorie, un tas de Fibonacci permet O(E + V log V), mais l’overhead le rend peu attractif en pratique.

#Pièges et variantesCopier le lien

• Multi‑sources: initialiser la PQ avec toutes les sources à 0.
• Densité élevée: un tableau des distances + choix naïf donne O(V^2) acceptable sur petits graphes denses.
• Graphes orientés vs non orientés: bien définir les arêtes; ne pas doubler par erreur.

#Mini‑quizCopier le lien