Dijkstra mit einem Heap
Greedy-Kürzestpfade auf Kanten mit nichtnegativen Gewichten
Dijkstra mit einem Heap ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Kürzeste-Wege-Problem
Sie möchten die kostengünstigste Route von einem Knoten zu jedem anderen Knoten finden. Dijkstra löst dieses Problem, wenn alle Kantengewichte null oder positiv sind.
Die Greedy-Idee
Dijkstra arbeitet greedy: Der Algorithmus erweitert immer den noch nicht besuchten Knoten mit der kleinsten bekannten Entfernung und vertraut darauf, dass diese Entfernung endgültig ist.
Warum ein Min-Heap
Um den nächstgelegenen Knoten schnell zu ermitteln, benötigen Sie einen Min-Heap. Er liefert die kleinste Entfernung in logarithmischer Zeit statt durch ein langsames Durchsuchen.
import heapqMit Entfernungen beginnen
Setzen Sie jede Entfernung auf Unendlich und die des Startknotens auf null. Nicht erreichte Knoten behalten einfach dauerhaft den Wert Unendlich.
dist = [float('inf')] * n
dist[src] = 0Den Heap initialisieren
Fügen Sie den Startknoten als Tupel aus (Entfernung, Knoten) ein. Weil die Entfernung an erster Stelle steht, ordnet der Heap die Einträge automatisch nach den Kosten.
pq = [(0, src)]Den nächstgelegenen Knoten entnehmen
Entnehmen Sie in jeder Schleifenrunde das kleinste (d, u) mit pop. d ist die kürzeste Entfernung zu u, daher ist die Verarbeitung von u nach dem Entnehmen abgeschlossen.
d, u = heapq.heappop(pq)Veraltete Einträge überspringen
Ein Knoten kann mit einer alten, größeren Entfernung im Heap liegen. Überspringen Sie diesen Eintrag, wenn d größer als die gespeicherte Entfernung ist.
if d > dist[u]:
continueNachbarn relaxieren
Relaxieren bedeutet, eine Verbesserung für einen Nachbarn zu versuchen: Wenn der Weg über u günstiger ist, aktualisieren Sie seine Entfernung und fügen ihn in den Heap ein.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Der Trick mit der verzögerten Löschung
Python-Heaps können einen Schlüssel nicht aktualisieren. Deshalb fügen Sie Duplikate ein und ignorieren veraltete Einträge. Dieser lazy Ansatz hält den Code kurz und schnell.
Die Laufzeit
Mit einem binären Heap läuft Dijkstra in O((V + E) log V). Damit lassen sich problemlos Graphen mit mehreren hunderttausend Kanten verarbeiten.
Auf die Kantengewichte achten
Dijkstra funktioniert bei negativen Kanten nicht, weil eine entnommene Entfernung dann möglicherweise doch nicht endgültig ist. Verwenden Sie in diesem Fall stattdessen Bellman-Ford.
Schnelltest
Sie entnehmen (d, u), aber d ist größer als dist[u]. Was sollten Sie tun?
Zusammenfassung: Dijkstra mit einem Heap
Sie initialisieren die Entfernungen, fügen (dist, node) ein, entnehmen den nächstgelegenen Knoten, überspringen veraltete Entnahmen und relaxieren die Nachbarn. Das ist Dijkstra in O((V+E) log V). 🚀
Häufig gestellte Fragen
Ist die Lektion „Dijkstra mit einem Heap“ kostenlos?
Ja — der vollständige Text von „Dijkstra mit einem Heap“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Dijkstra mit einem Heap“?
Greedy-Kürzestpfade auf Kanten mit nichtnegativen Gewichten Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Dijkstra mit einem Heap“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Dijkstra mit einem Heap
- 0-1 BFS mit einer Deque
- Bellman-Ford und negative Kanten
- Floyd-Warshall für alle Paare