Dijkstra-Algorithmus: Kürzeste Wege in Graphen zuverlässig berechnen

Der Dijkstra-Algorithmus berechnet die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen — vorausgesetzt, alle Kantengewichte sind nicht negativ. Entwickelt wurde er 1956 vom niederländischen Informatiker Edsger W. Dijkstra und 1959 veröffentlicht; er gehört zu den bekanntesten Algorithmen der Informatik.

Wo er überall steckt

Navigationsgeräte und Routenplaner berechnen mit Dijkstra-Varianten die schnellste Strecke. Auch Netzwerk-Routingprotokolle wie OSPF nutzen das Verfahren, um günstige Wege durch das Netz zu finden — die Netztopologie liegt dabei als Adjazenzliste oder Adjazenzmatrix vor.

So funktioniert er

  1. Der Startknoten erhält die Distanz 0, alle anderen unendlich.
  2. Ein Heap (Prioritätswarteschlange) enthält die noch nicht abgeschlossenen Knoten, sortiert nach ihrer aktuellen Distanz.
  3. Der Knoten mit der kleinsten Distanz wird entnommen und abgeschlossen.
  4. Für jeden Nachbarn wird geprüft, ob der Weg über den aktuellen Knoten kürzer ist als der bisher bekannte; wenn ja, wird die Distanz aktualisiert und der Nachbar neu in den Heap einsortiert.
  5. Schritte 3 und 4 wiederholen sich, bis alle Knoten abgeschlossen sind.

Beispiel in Python

import heapq

def dijkstra(start, graph):
    dist = {k: float("inf") for k in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, gewicht in graph[u]:
            neu = d + gewicht
            if neu < dist[v]:
                dist[v] = neu
                heapq.heappush(heap, (neu, v))
    return dist

Komplexität und Grenzen

  • Laufzeit: mit einem Binär-Heap O((V + E) · log V) — V Knoten, E Kanten.
  • Grenze: Bei negativen Kantengewichten liefert der Algorithmus falsche Ergebnisse; dann kommt der Bellman-Ford-Algorithmus zum Einsatz. Gegen negative Zyklen hilft auch der nicht.
  • Verwandtschaft: Vom Ablauf her ähnelt der Algorithmus einer gewichteten Breitensuche, wie sie die Traversierung von Graphen beschreibt.