Graphenalgorithmen

Problem

Gegeben ist ein ungerichteter, zusammen­hängender Graph mit einer Kanten­gewichtung. Gesucht sind die kürzesten Wege von einem bestimmten Startknoten zu allen anderen Knoten des Graphen.

Der Floyd-Algorithmus löst das Problem mit der Zeit­komplexität Θ(n³). Er berechnet aber sogar die kürzesten Wege von allen Knoten zu allen anderen Knoten.

Wenn nur die kürzesten Wege von einem bestimmten Startknoten zu allen anderen Knoten gesucht sind, lässt sich das Problem mit dem Algorithmus von Dijkstra [Dij 59] in Zeit Θ(n²) lösen.

Idee

Der Algorithmus zur Berechnung der kürzesten Wege baut schrittweise den Baum der kürzesten Wege auf. Jedes Mal, wenn ein neuer Knoten u zum Baum hinzukommt, muss die Menge der Kandidaten aktualisiert werden. Hierzu werden alle Nachbar­knoten von u durchlaufen. Dabei kommt es nun darauf an, wie viele Nachbar­knoten die Knoten des Graphen typischer­weise haben. Sind dies viele, etwa Θ(n) , so kann "alle Nachbar­knoten durchlaufen" ersetzt werden durch "alle Knoten durchlaufen".

Damit ergibt sich ein einfacheres und schnelleres Verfahren, das zudem ohne Prioritäten­liste auskommt, das Verfahren von Dijkstra.

Es stellt sich heraus, dass sich der Dijkstra-Algorithmus durch eine geringfügige Modifikation des Algorithmus zu Berechnung eines minimalen Spannbaums ergibt. Die Änderung betrifft die Wahl des nächsten Kandidaten, der zu dem jeweils schon erzeugten Baum hinzu­genommen wird. Bei der Berechnung des Baums der kürzesten Wege wird der Kandidat genommen, der den kürzesten Abstand zum Startknoten hat. Dieser Abstand ergibt sich aus dem Gewicht der Kante zwischen dem Kandidaten und einem Knoten des schon erzeugten Baumes plus dem Abstand dieses Knotens vom Startknoten.

Algorithmus Kürzeste Wege

Der Algorithmus zur Berechnung der kürzesten Wege ist fast identisch mit dem Algorithmus zur Berechnung eines minimalen Spannbaums. Die einzigen Abweichungen sind in der folgenden informellen Darstellung fett gedruckt gekenn­zeichnet.

Algorithmus Kürzeste Wege (Dijkstra)

Eingabe:

Zusammenhängender ungerichteter Graph G = (V, E) mit Kantengewichtung w, Startknoten s

Ausgabe:

Baum der kürzesten Wege in G vom Startknoten s zu allen anderen Knoten; zu jedem Knoten v bedeuten distance(v) die kürzeste Entfernung zum Startknoten und predecessor(v) den zugehörigen Vorgänger im Baum

Methode:

1. für alle v ∈ V wiederhole
1. setze distance(v) = ∞

setze u = s

setze T = {u}

setze distance(u) = 0

setze predecessor(u) = -1

solange T ≠ V wiederhole

1. für alle v ∉ T mit (u, v) ∈ E wiederhole
1. wenn distance(v) > distance(u) + w(u, v) dann
1. setze distance(v) = distance(u) + w(u, v)

setze predecessor(v) = u

suche u ∉ T mit distance(u) minimal

setze T = T ∪ {u}

Das entsprechende Java-Programm ergibt sich mit den angegebenen Änderungen unmittelbar aus dem Programm zur Berechnung eines minimalen Spannbaums.

Literatur

Originalartikel:

[Dij 59]   E.W. Dijkstra: A Note on two Problems in Connexion with Graphs. Numerische Mathematik 1, 269-271 (1959)

Bücher