Dijkstra avec un tas
Calculer gloutonnement les plus courts chemins sur des arêtes non négatives
Dijkstra avec un tas est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème du plus court chemin
Vous cherchez le chemin le moins coûteux d'un nœud vers tous les autres. Dijkstra résout ce problème lorsque le poids de chaque arête est nul ou positif.
L'idée gloutonne
Dijkstra est glouton : il développe toujours le nœud non visité dont la distance connue est la plus petite, en considérant cette distance comme définitive.
Pourquoi utiliser un tas min
Pour récupérer rapidement le nœud le plus proche, vous avez besoin d'un tas min. Il vous fournit la distance minimale en temps logarithmique en n, au lieu d'effectuer un parcours lent.
import heapqCommencer par les distances
Initialisez chaque distance à l'infini, puis attribuez zéro à la source. Les nœuds inatteignables restent simplement à l'infini pour toujours.
dist = [float('inf')] * n
dist[src] = 0Initialiser le tas
Insérez la source sous la forme d'un couple (distance, nœud). Placer la distance en premier permet au tas d'ordonner automatiquement les entrées selon leur coût.
pq = [(0, src)]Retirer le nœud le plus proche
À chaque itération, retirez le plus petit couple (d, u). Cette valeur d est la plus courte distance jusqu'à u : son traitement est donc terminé dès son retrait.
d, u = heapq.heappop(pq)Ignorer les entrées obsolètes
Un nœud peut se trouver dans le tas avec une ancienne distance plus élevée. Ignorez-le lorsque d est supérieure à la distance enregistrée.
if d > dist[u]:
continueRelâcher les voisins
Le relâchement consiste à essayer d'améliorer la distance d'un voisin : si passer par u coûte moins cher, mettez sa distance à jour et insérez-le dans le tas.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))L'astuce de la suppression paresseuse
Les tas de Python ne peuvent pas mettre à jour une clé : vous insérez donc des doublons et ignorez les entrées obsolètes. Ce style paresseux rend le code court et rapide.
Le temps d'exécution
Avec un tas binaire, Dijkstra s'exécute en O((V + E) log V). Cette complexité suffit largement pour des graphes comportant des centaines de milliers d'arêtes.
Surveiller les poids des arêtes
Dijkstra échoue avec des arêtes négatives, car une distance retirée du tas peut ne pas être définitive. Dans ce cas, utilisez plutôt Bellman-Ford.
Vérification rapide
Vous retirez (d, u), mais d est supérieure à dist[u]. Que devez-vous faire ?
Récapitulatif : Dijkstra avec un tas
Vous initialisez les distances, insérez (dist, nœud), retirez le nœud le plus proche, ignorez les retraits obsolètes et relâchez les voisins. Voilà Dijkstra en O((V+E) log V). 🚀
Questions Fréquemment Posées
La leçon « Dijkstra avec un tas » est-elle gratuite ?
Oui — le texte complet de « Dijkstra avec un tas » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Dijkstra avec un tas » ?
Calculer gloutonnement les plus courts chemins sur des arêtes non négatives Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Dijkstra avec un tas » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Dijkstra avec un tas
- BFS 0-1 avec une deque
- Bellman-Ford et arêtes négatives
- Floyd-Warshall entre toutes les paires