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.
Operation | lineare Suche | Heap |
Einfügen eines Knotens | entfällt | O(log n) |
Aktualisieren eines Knotens | entfällt | O(log n), up oder down bubbling |
Minimum suchen | O(n) | O(log n), Wurzel entfernen |
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:
Knoten | Kanten | Kanten pro Knoten | Zeitaufwand | |
lineare Suche | Suche mit Heap | |||
50000 | 400000 | 8 | 1327 s | 17 s |
1500 | 850000 | 567 | 5 s | 3 s |
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.
Programm | Beschreibung |
dijkstra.c | der Dijkstra Algorithmus, mit linearer Knotensuche |
graphio.h | die Bibliothek zum Einlesen und Speichern von Graphen |
graphio.c | |
dijkheap.c | der Dijkstra Algorithmus, mit Priorityqueue |
heap.h | Verwaltung einen Priorityqueue mit long Einträgen mit Hilfe eines Heap |
heap.c |
Zum Thema Dijkstra-Algorithmus gibt es im Download-Bereich auch einen Vortrag von mir.
Zurück zur Hauptseite Computerorientierte Mathematik.