Dijkstras Algorithmus erklärt, Schritt für Schritt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Was ist Dijkstras Algorithmus?

Dijkstras Algorithmus, 1959 von Edsger W. Dijkstra veröffentlicht, findet den kürzesten Weg von einer einzigen Quelle zu jedem anderen Knoten in einem gewichteten Graphen. Er funktioniert sowohl bei gerichteten als auch bei ungerichteten Graphen, mit einer festen Bedingung: jedes Kantengewicht muss nichtnegativ sein.

Stellen Sie sich den Graphen als Straßennetz vor. Knoten sind Kreuzungen, Kanten sind Straßen, und jedes Gewicht ist die Zeit oder Entfernung, um diese Straße zu befahren. Dijkstras Algorithmus beantwortet die Frage, die jede Navigations-App stellt: Was ist die schnellste Route von meinem Standort zu allen anderen? Er ist ein Eintrag in der größeren Familie, die in Algorithmen für kürzeste Wege behandelt wird, und fester Bestandteil des Graphentheorie-Lernpfads.

Die Grundidee

Dijkstras Algorithmus ist gierig. Er hält für jeden Knoten eine vorläufige kürzeste Distanz und wiederholt einen einfachen Schritt:

Besuche stets den unbesuchten Knoten mit der kleinsten bekannten Distanz und nutze ihn, um seine Nachbarn zu verbessern.

Die Einsicht, die das korrekt macht: Weil alle Gewichte nichtnegativ sind, kann kein zukünftiger Weg den nächstgelegenen unbesuchten Knoten günstiger erreichen, sobald man ihn gewählt hat. In dem Moment, in dem ein Knoten gewählt wird, ist seine Distanz also endgültig. Diese eine Garantie ist der ganze Algorithmus.

Konkret verwaltet der Algorithmus:

• Eine Distanz zu jedem Knoten, alle beginnen bei unendlich, außer der Quelle, die 0 ist.
• Eine Prioritätswarteschlange (Min-Heap), die stets den nächstgelegenen unbesuchten Knoten zurückgibt.
• Eine Menge endgültiger Knoten, deren kürzeste Distanz feststeht.

Das Verbessern eines Nachbarn heißt Relaxation: Ist der Weg über den aktuellen Knoten kürzer als die gespeicherte Distanz des Nachbarn, senkt man sie.

So funktioniert er, Schritt für Schritt

Lassen wir Dijkstra vom Knoten A auf diesem gewichteten Graphen laufen. Die blauen Kanten bilden den endgültigen Kürzeste-Wege-Baum, und die Zahl neben jedem Knoten ist seine endgültige kürzeste Distanz von A.

Hier ist der Ablauf. In jedem Schritt legen wir den nächstgelegenen unbesuchten Knoten endgültig fest (fett) und relaxieren seine Nachbarn. ∞ bedeutet "noch nicht erreicht".

Beachten Sie Schritt drei: Der Besuch von C senkte B von 4 auf 3, weil die Route A → C → B (2 + 1) die direkte Kante A → B (4) schlägt. Das ist Relaxation bei der Arbeit. Dies auf einem Live-Graphen ablaufen zu sehen, macht das Muster sofort klar, was Sie im Algorithmen-Visualisierer tun können.

Implementierung in Python

Die saubere, interviewreife Version verwendet Pythons heapq als Prioritätswarteschlange. Der Graph ist eine Adjazenzliste, die jeden Knoten auf eine Liste von (Nachbar, Gewicht)-Paaren abbildet.

import heapq

def dijkstra(graph, start):
    # Jeder Knoten beginnt unendlich weit entfernt, außer der Quelle.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (bisherige Distanz, Knoten)

    while pq:
        dist, node = heapq.heappop(pq)

        # Ein veralteter, längerer Eintrag für einen bereits festgelegten Knoten: überspringen.
        if dist > distances[node]:
            continue

        for neighbour, weight in graph[node]:
            new_dist = dist + weight
            # Relaxation: einen günstigeren Weg zum Nachbarn gefunden.
            if new_dist < distances[neighbour]:
                distances[neighbour] = new_dist
                heapq.heappush(pq, (new_dist, neighbour))

    return distances

Zwei Details sind wichtig. Erstens fügen wir einen neuen Eintrag hinzu, statt den Heap direkt zu aktualisieren, und überspringen dann veraltete Einträge mit der Prüfung dist > distances[node]. Dieses "faule Löschen" hält den Code einfach und ist gängige Praxis. Zweitens berechnet der Algorithmus von Natur aus Distanzen zu allen Knoten; um bei einem einzigen Ziel früh zu stoppen, geben Sie zurück, sobald Sie es entnehmen.

Zeit- und Speicherkomplexität

Die Kosten hängen von der Prioritätswarteschlange ab. Jede Kante kann höchstens ein Einfügen auslösen, und jedes Einfügen oder Entnehmen bei einem binären Heap kostet O(log V).

Der Speicher ist O(V) für die Distanztabelle plus die Warteschlange. Für die Begründung dieser Schranken und ihren Vergleich über alle Graphenalgorithmen hinweg siehe den Leitfaden zur Komplexität von Graphenalgorithmen und den einseitigen Spickzettel.

Wann Dijkstra versagt: negative Gewichte

Die gierige Garantie beruht ganz auf nichtnegativen Gewichten. Fügen Sie eine negative Kante hinzu, und das Ganze kann zusammenbrechen.

Angenommen, der Algorithmus legt einen Knoten endgültig fest, weil er am nächsten scheint, Distanz 5. Später entdeckt er eine länger wirkende Route, die über eine -4-Kante führt und diesen Knoten tatsächlich in 3 erreicht. Zu spät: Dijkstra hat 5 bereits für endgültig erklärt und ist weitergezogen. Die Antwort ist falsch.

Merkregel: nichtnegative Gewichte, nimm Dijkstra. Jedes negative Gewicht, nimm Bellman-Ford, der jede Kante wiederholt relaxiert und auch negative Zyklen erkennen kann.

Dijkstra im Vergleich zu anderen Algorithmen

Dijkstra ist eines von mehreren Werkzeugen. Das richtige auszuwählen, hängt vom Graphen ab.

Der nächste Verwandte ist die A*-Suche, also Dijkstra plus eine Heuristik, die die Suche auf ein einziges Ziel lenkt. Und Dijkstra selbst ist eigentlich Breitensuche, aufgerüstet von einer einfachen Warteschlange zu einer Prioritätswarteschlange.

Anwendungen in der Praxis

• Navigation und Karten: die kürzeste oder schnellste Route zwischen zwei Orten, der klassische Einsatz.
• Netzwerk-Routing: Link-State-Protokolle wie OSPF nutzen Dijkstra, um Weiterleitungstabellen zu berechnen.
• Spiele und Robotik: Bewegungskosten über eine Karte, oft mit A* darauf aufgesetzt.
• Betrieb und Logistik: kostenminimale Wege in Liefer-, Telekom- und Verkehrsnetzen, ein Grundpfeiler des Operations Research.