Dijkstra-Algorithmus / Kürzeste Wege

Google Maps macht es 8 Milliarden Mal am Tag: berechne die schnellste Route von A nach B. Der Standard-Algorithmus dafür ist Dijkstra. Er findet in einem gewichteten Graphen den kürzesten Pfad von einem Startknoten zu allen anderen. Klausur-Pflicht in 14/17 WInf-Algorithmen-Klausuren.

Die Idee in einem Satz

Dijkstra: Vom Startknoten ausgehend nimmst du immer den noch unbesuchten Knoten mit der kürzesten bekannten Entfernung, fügst ihn zum "fertigen" Set hinzu und aktualisierst von dort aus die Entfernungen zu seinen Nachbarn.

Beispiel: Mini-Graph

        4
   A ─────── B
   │ \       │
   │  \ 2    │ 5
 1 │   \     │
   │    \    │
   │     \   │
   C ─────── D
        3

Kanten: A-B (4), A-C (1), A-D (2), B-D (5), C-D (3).

Start: A. Frage: kürzeste Entfernung zu jedem Knoten?

Aber: A → D (2) ist kürzer als A → C → D (1 + 3 = 4). Dijkstra findet das automatisch.

Schritte des Algorithmus

Setup:

• dist[v] = ∞ für alle Knoten außer Start
• dist[start] = 0
• Priority Queue mit allen Knoten

Loop:

1. Entnimm Knoten u mit kleinstem dist[u]
2. Markiere u als "fertig"
3. Für jeden Nachbarn v von u (noch nicht fertig):
   • Berechne alt = dist[u] + gewicht(u, v)
   • Wenn alt < dist[v]: dist[v] = alt, vorgänger[v] = u (Relax-Schritt)

Bis PQ leer oder Ziel erreicht.

Pseudocode

dijkstra(graph, start):
    for v in graph.nodes:
        dist[v] = infinity
        prev[v] = null
    dist[start] = 0
    pq = PriorityQueue(all nodes with dist as key)

    while pq not empty:
        u = pq.extractMin()
        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                pq.decreaseKey(v, alt)

Komplexität

Standard-Klausur-Antwort: O((V + E) log V) mit Binary Heap.

Wichtige Voraussetzung

Dijkstra funktioniert NUR bei nicht-negativen Kantengewichten.

Bei negativen Kanten: nutze Bellman-Ford (O(V · E)). Bei negativen Zyklen ist "kürzester Weg" überhaupt nicht definiert (du könntest unendlich oft im Zyklus laufen).

Klausur-Falle: Manche Aufgaben tarnen negative Gewichte als "Profit", "Nutzen", "Diskont", vorsichtig lesen.

Pfad-Rekonstruktion

Dijkstra speichert nur Distanzen + Vorgänger. Für den eigentlichen Pfad zu Knoten z:

path = []
current = z
while current != null:
    path.prepend(current)
    current = prev[current]

Du folgst dem Vorgänger-Pfeil rückwärts vom Ziel zum Start.

Vergleich zu BFS

• BFS: kürzester Pfad in UNGEWICHTETEN Graphen (Kantenanzahl)
• Dijkstra: kürzester Pfad in GEWICHTETEN Graphen (nicht-negative Gewichte)
• Bellman-Ford: wie Dijkstra, aber auch negative Gewichte erlaubt
• A*: Dijkstra + Heuristik (Goal-aware, schneller in der Praxis)

BFS ist im Prinzip Dijkstra mit Kantengewicht 1.

Klausur-Faustregeln

1. Tabelle führen: dist + prev für jeden Knoten. Bei jedem Schritt aktualisieren. Klausur-Standard.

2. Aus PQ den Knoten mit min(dist) ziehen. Wichtig: BEKANNTE Distanz, nicht "geschätzt".

3. Relax-Schritt: dist[v] = min(dist[v], dist[u] + w(u,v)). Update nur wenn neuer Weg kürzer.

4. O((V+E)log V) mit Binary Heap. Standard-Komplexität.

5. NUR nicht-negative Gewichte. Bei negativen → Bellman-Ford.

Häufige Stolpersteine

1. Knoten zweimal aus PQ ziehen. Sobald ein Knoten "fertig" markiert ist, NICHT mehr aktualisieren. Manche Implementierungen ohne decreaseKey ziehen einen Knoten mehrfach, dann ignorieren wenn schon fertig.

2. Negative Gewichte ignoriert. Bei der Klausur IMMER prüfen: "sind alle Kantengewichte ≥ 0?" Wenn nein, Dijkstra falsch.

3. Pfad-Rekonstruktion umgekehrt. Du folgst prev rückwärts vom Ziel, vergiss nicht zu reversen oder vorne anzufügen.

4. Dijkstra mit Tiefensuche verwechseln. Dijkstra ist eine Form von Greedy + Priority-Queue + Best-First-Search, NICHT Tiefensuche (DFS).

5. Dist statt Vorgänger updaten. Beim Relax-Schritt MUSS sowohl dist[v] als auch prev[v] aktualisiert werden, sonst geht die Pfad-Info verloren.

Dijkstra-Graph-Stepper

Geh durch das klassische Dijkstra-Beispiel Schritt für Schritt. Pro Schritt siehst du:

• Die Distanz-Tabelle mit aktuellen dist- und prev-Werten
• Den gerade extrahierten Knoten und seine Nachbarn
• Die Relax-Operationen (gelb hervorgehoben)
• Den fertigen Pfad am Ende

Probier verschiedene Start-Knoten aus.

Klausur-Tipp: Bei Dijkstra-Aufgaben IMMER eine Tabelle mit dist + prev anlegen und in jeder Iteration explizit aktualisieren. Markiere den aktuellen Knoten, die Nachbarn die geprüft werden, und die tatsächlichen Updates. Spart Verwirrung und gibt Teilpunkte bei Rechenfehlern.

Dijkstra, Praxis-Übung

6 Aufgaben zu Algorithmus-Schritten, Komplexität, Voraussetzungen.