Dijkstra-Algorithmus

Viele kürzeste Wege Algorithmen basieren darauf, zu entscheiden, ob der Weg kürzer wird, wenn ein "Umweg" über einen weiteren Knoten gemacht wird.

  gegeben ist ein Weg (u, v)
  wenn Länge (u, w) + (w, v) ist kürzer als Länge (u, v) dann
    setze Weg (u, v) auf (u, w) + (w, v)

Die Algorithmen unterscheiden sich im Wesentlichen nur in der Reihenfolge der Wahl der getesteten Knoten u, v und w.

Ein einfacher Greedyalgorithmus, der nur für nicht-negative Kantengewichte funktioniert ist der Dijkstra Algorithmus. Dieser verwendet zwei Felder, um zu jedem Knoten den Vorgänger (pre) auf einem kürzesten Weg zu speichern, und die Länge (dist) dieses Weges. Das ist ganz allgemein die einfachste Möglichkeit eine Aboreszenz, d.h. einen Kürzeste-Wege-Baum zu speichern.

Des weiteren müssen die Knoten markierbar sein. Die markierten Knoten sind diejenigen, für die der kürzeste Weg schon bekannt ist. Das Greedy-Verhalten besteht darin, immer den unmarkierten Knoten auszuwählen, der den geringsten Abstand hat (dazu mehr unten, siehe Grafik). Dieser wird markiert, und nach obigem Schema wird getestet, ob sich ein Weg verkürzt, wenn man über diesen Knoten geht. Genauer: wenn eine Kante benutzt wird, die von diesem Knoten wegführt.

  algorithm disjkstra
  input D = (V, A)   - ein Digraph
        w(a)  a  A - eine Gewichtsfunktion
        s  V        - Startknoten

    pre, dist - zwei Felder
    pre[v] := s   v  V
    dist[v] :=   v  V

    dist[s] := 0

    for i:=1 to V do
      select u  V not visited
             dist[u] = min(dist[v]  v  V not visited)
      if dist[u] =  then
        return      ; alle anderen Knoten sind auch unerreichbar
      visit(u)                                ; Knoten markieren
      forall (u,v)  A do
        if dist[v] > dist[u] + w((u,v)) then  ; Umweg kürzer ?
          dist[v] := dist[u] + w((u,v))
          pre[v] := u                         ; kürzerer Vorgänger

Zur Auswertung muss die Vorgängerstruktur abgearbeitet werden. Der Vorgänger eines kürzesten Weges nach v ist pre[v]. D.h. der kürzeste Weg besteht aus dem kürzesten Weg nach pre[v] und der Kante (pre[v], v) (eine hübsche rekursive Beschreibung). Fehlt noch der Rekursionsabbruch: der ürzeste Weg nach s besteht nur aus dem Knoten s. Ist ein Knoten nicht erreichbar, dann ist dist[v] = . Das sollte vorher überprüft werden. Auch der Algorithmus ist daraufhin optimiert: ist der Abstand des gewählten Knoten unendlich, dann sind das auch alle anderen Abstände und der Algorithmus ist fertig.

Ein Gegenbeispiel, an dem zu sehen ist, was bei negativen Kantengewichten passiert. Die Greedyauswahl (Knoten u hat den geringsten Abstand von der markierten Knotenmenge) funkioniert nur, wenn der Weg über andere unmarkierte Knoten nur länger werden kann. Der Abstand zu allen anderen unmarkierten Knoten v ist länger als der nach u. Und das Gewicht eines Weges von v nach u ist nicht negativ. Damit sind alle Wege über v nach u länger als die Kante, die der Algorithmus gewählt hat und die Auswahl ist korrekt.

Das grösste Problem des Algorithmus besteht in der Auswahl des unmarkierten Knoten mit minimalem Abstand. Die einfachste Möglichkeit (die in dijkstra.c implementiert ist) besteht darin, das Feld dist linear nach dem Minimum zu durchsuchen. Da jeder Knoten einmal gewählt wird, ist der Gesamtaufwand quadratisch.

Besser ist die Verwendung einer Prioritätswarteschlange (implementiert über einen Heap in dijkheap.c). Ein Heap ist eine Baumstruktur, bei dem der Wurzelknoten immer das kleinste Gewicht hat. Es wird jeder Knoten im Heap aufgenommen, bei der Verkürzung eines Weges, muss der Wert im Heap aktualisiert werden. Dafür kann die Prioritätsschlange sehr effektiv das Minimum suchen.

Enthält der Graph sehr viel mehr (quadratisch viele) Kanten als Knoten, dann überwiegt der Aufwand, die Warteschlange zu aktualisieren. Besteht der Graph aber aus relativ wenig Kanten (d.h. Kantengrad der Knoten ist beschränkt), dann ergibt sich bei der Warteschlange ein Gesamtaufwand von O(n log n). Ein kleiner Test mit zwei Graphen (auf einem sehr langsamen Testrechner) ergab diese Werte:

Zum Vergleich, auf einem P4 1.8 GHz braucht dijkheap für den ersten Graphen 0.2 Sekunden. Gemessen wurde nur die Zeit des Algorithmus, ohne Einlesen des Graphen und ohne Ausgabe. Beim ersten Graphen, mit relativ wenig Kanten ist der Effekt deutlich sichtbar. Beim zweiten Graphen ist das Ergebnis schon relativ knapp. Bei einem vollständigen Graphen würde sich das Zeitverhalten auch umkehren.

Zum Thema Dijkstra-Algorithmus gibt es im Download-Bereich auch einen Vortrag von mir.

Zurück zur Hauptseite Computerorientierte Mathematik.