Dijkstras Algorithmus mit einer Priority Queue

Dijkstras Algorithmus findet den kürzesten Weg von einem einzelnen Startknoten zu allen anderen Knoten in einem gewichteten Graphen mit nichtnegativen Kantengewichten. Dazu werden die Knoten gierig in der Reihenfolge ihrer aktuell besten bekannten Distanz verarbeitet – stets wird der nächstgelegene noch nicht besuchte Knoten erweitert. Die entscheidende Datenstruktur ist ein Min-Heap (Prioritätswarteschlange), der effizient den Knoten mit der kleinsten Distanz liefert.

Dijkstras Algorithmus: (1) Initialisieren Sie dist[source] = 0 und dist[all others] = inf. (2) Legen Sie (0, source) in einen Min-Heap. (3) Entfernen Sie den Knoten u mit der kleinsten Distanz. Wenn er bereits mit einer kleineren Distanz besucht wurde, überspringen Sie ihn. (4) Prüfen Sie für jeden Nachbarn v von u: Falls dist[u] + weight(u,v) < dist[v] gilt, aktualisieren Sie dist[v] und legen Sie (dist[v], v) in den Heap. (5) Wiederholen Sie dies, bis der Heap leer ist.

Das Python-Modul heapq implementiert einen Min-Heap. Wir stellen den Graphen als Adjazenzliste dar: graph[u] = [(v, weight), ...]. Der Heap speichert Tupel der Form (distance, node). Wir verwenden eine visited-Menge, um veraltete Heap-Einträge zu überspringen – also Einträge, die hinzugefügt wurden, bevor ein besserer Weg gefunden wurde.

Betrachten Sie einen Graphen mit 5 Knoten und den Kanten: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Die kürzesten Wege vom Knoten 0 sind: zu 1 über 0→2→1 mit den Kosten 3, zu 2 mit den Kosten 1, zu 3 über 0→2→1→3 mit den Kosten 4 und zu 4 über 0→2→1→3→4 mit den Kosten 7. Dijkstra findet alle diese Wege in einem Durchlauf, nicht nur den Weg zu einem einzelnen Zielknoten.

Die Korrektheit von Dijkstra beruht darauf, dass die Distanz eines Knotens endgültig ist, sobald er aus dem Min-Heap entnommen wird. Das gilt nur, wenn die Kantengewichte nichtnegativ sind. Bei einer negativen Kante u→v mit dem Gewicht -5 könnten wir nach dem Besuch von v einen kürzeren Pfad über u finden – aber v ist bereits als besucht markiert. Eine einzige negative Kante kann alle nachfolgenden Distanzberechnungen ungültig machen.

Dieses Problem fügt eine Einschränkung hinzu: höchstens k Zwischenstopps. Der standardmäßige Dijkstra-Algorithmus verarbeitet die Anzahl der Schritte nicht direkt. Lösung: Erweitern Sie den Zustand zu (cost, node, stops_remaining). Verwenden Sie Dijkstra mit diesem 3-Tupel oder Bellman-Ford mit k+1 Relaxierungsdurchläufen. Der modifizierte Dijkstra-Algorithmus stoppt, sobald stops_remaining 0 erreicht, und verhindert so weitere Sprünge.

Mit einem Binär-Heap läuft Dijkstra in O((V + E) log V) Zeit: Jeder Knoten wird einmal entnommen (V Entnahmen), jede Kante kann einen Push auslösen (E Pushes), und jede Heap-Operation kostet O(log V). Mit einem Fibonacci-Heap verbessert sich die Schranke auf O(E + V log V), aber Python's heapq ist ein Binär-Heap. Für dünn besetzte Graphen (E ≈ V) hat die Binär-Heap-Version die Komplexität O(V log V); für dichte Graphen (E ≈ V²) beträgt sie O(V² log V).

Um den tatsächlichen Pfad und nicht nur die Distanzen zu ermitteln, verwalten Sie ein prev-Array: Setzen Sie beim Aktualisieren von dist[v] den Wert prev[v] = u. Nach Abschluss des Algorithmus rekonstruieren Sie den Pfad von der Quelle zum Ziel, indem Sie rückwärts zurückverfolgen: Beginnen Sie bei dst, folgen Sie den prev-Zeigern bis zu source und kehren Sie anschließend die Reihenfolge des Ergebnisses um.

Wenn Knoten Strings oder nicht zusammenhängende Ganzzahlen sind, verwenden Sie eine defaultdict(list) für die Adjazenzliste und ein gewöhnliches dict für die Distanzen. Dies ist in LeetCode-Problemen wie Network Delay Time üblich, bei denen die Knoten mit 1 bis n beschriftet sind. Denken Sie daran, dist = {node: inf for node in all_nodes} zu verwenden und nach dem Algorithmus auf nicht erreichbare Knoten zu prüfen.

Für ungewichtete Graphen findet BFS kürzeste Pfade in O(V + E) – schneller als Dijkstras O((V+E) log V). Dijkstra verallgemeinert BFS auf gewichtete Graphen, indem eine Prioritätswarteschlange anstelle einer gewöhnlichen FIFO-Warteschlange verwendet wird. Wenn alle Kantengewichte gleich sind, wird Dijkstra zu BFS. Verwenden Sie BFS für ungewichtete Graphen, Dijkstra für nichtnegative Gewichte und Bellman-Ford für negative Gewichte.

Der Dijkstra-Algorithmus aus Lehrbüchern verwendet eine Prioritätswarteschlange mit decrease-key: Wenn sich die Distanz eines Knotens verbessert, wird seine Priorität direkt aktualisiert. Dafür wäre ein Fibonacci-Heap erforderlich, um O(E + V log V) zu erreichen, die Implementierung ist jedoch schwierig. Beim in Interviews verwendeten Ansatz der Lazy Deletion wird stattdessen ein neuer Eintrag eingefügt und veraltete Entnahmen werden übersprungen – einfacher, bei nur konstantem Mehraufwand. In Python ist Lazy Deletion mit heapq die übliche Implementierung in Interviews.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie gelernt: Dijkstra verwendet einen Min-Heap, um Knoten in der Reihenfolge ihrer aktuell besten Distanz gierig zu verarbeiten, läuft in O((V+E) log V) Zeit und scheitert bei Kanten mit negativen Gewichten und veraltete Heap-Einträge werden durch die Prüfung einer Menge besuchter Knoten beim Entnehmen behandelt. Als Nächstes behandeln wir Bellman-Ford, der negative Gewichte durch n-1 Relaxierungsdurchläufe verarbeitet.