Overview
L'algorithme de Dijkstra trouve le chemin le plus court depuis une source vers tous les autres nœuds dans un graphe à arêtes de poids non négatif.
Analogy
Comme GPS qui calcule le trajet le plus rapide — il explore toujours d'abord la route la moins coûteuse non encore confirmée.
Step-by-step
- Initialise les distances à l'infini sauf la source (0)
- Utilise une file de priorité (tas min)
- Extrais le nœud de distance minimale
- Mets à jour les voisins si un chemin plus court est trouvé
Visual
A=0 → B=4, C=2
C=2 → B=min(4,3)=3
B=3 → D=3+2=5
Common mistakes
- Utiliser sur des arêtes à poids négatif (utiliser Bellman-Ford)
- Oublier de pousser les distances mises à jour dans le tas
Practice questions
- Trouve le chemin le plus court sur une carte de ville
- Implémente avec un dictionnaire de liste d'adjacence