Projekt:Mathematik in Natur und Technik/dijkstra

Was ist der kürzeste Weg von Frankfurt nach München?

Mit Hilfe des Dijkstra Algorithmus berechnen Navigationsgeräte die kürzesten Wege zwischen zwei Punkten. Wie funktioniert er?

Zur Person

Edsger Wybe Dijkstra

Edgar Wybe Dijkstra wurde am 11.Mai 1930 in Rotterdam, Niederlande geboren und starb am 6. August 2002 an den Folgen von Krebs. Schon früh entwickelte Dijkstra eine Vorliebe zur Mathematik und Physik und studierte deshalb auch diese Fächer an der Universität Leiden, Niederlande. Während seiner Tätigkeit am Zentrum für Mathematik und Informatik in Amsterdam (1952 - 1962) entwickelte er 1959 den Dijkstra-Algorithmus und veröffentlichte diesen. Dies war nur eine seiner vielen Errungenschafften der modernen Mathematik. Er war Wegbereiter der strukturierten Programmierung und machte sich so im akademischen wie auch im industriellen Bereich einen Namen. Der Höhepunkt seiner Laufbahn war der ACM Turing Award, den er 1972 aufgrund seiner Arbeit zum Thema "Technik und Kunst der Programmiersprachen" verliehen bekam. Sein Interesse galt aber auch dem Unterrichten. So nahm er eine Stelle als Mathematikprofessor an der TU Eindhoven an und wechselte 1984 an die University of Texas in Austin, USA. Erst 1999 beendete er altersbedingt seine Karriere als Professor.

Einführung in die Graphentheorie

Der Dijkstra Algorithmus basiert auf der Graphentheorie. Diese kurze Einführung genügt, um den Dijkstra Algorithmus nachvollziehen zu können.

Ein Graph besteht aus Knoten und Kanten. Die Knoten (in Bild1: Städte) stellt man zeichnerisch als Punkte dar. Sie enthalten keine geometrische Informationen, das heißt sie sind frei verschiebbar. Eine Kante (in Bild1: Straßen) wird als Verbindungsstrecke zweier Punkte definiert. Die Kante kann gerichtet oder ungerichtet sein. Man kann sich eine gerichtete Kante als eine Einbahnstraße vorstellen (Laufrichtung für den Algorithmus vorgegeben), eine ungerichtete als "normale" Straße (Laufrichtung frei wählbar). Einer Kante ist ein Wert zugeordnet (gewichtet), entweder Distanz, Kosten oder Dauer. Im Beispiel "Suche nach der kürzesten Strecke von Frankfurt nach München" ist dies eine Distanz (in Bild1: Wegstrecke in km). Die Kantenlänge und Form, ob Kurve oder Gerade, hat jedoch nichts mit der Gewichtung zu tun. Man kann sich Kanten als dehnbare Gummifäden vorstellen.

Mathematische Darstellung:

Ein Graph wird mit $G=(V,E)$ bezeichnet, wobei

V(G)=\lbrace v_{i}\mid {\text{i=1, …, n}}\rbrace

die Knotenmenge und

E(G)=\lbrace e_{i,j}=\langle v_{i},v_{j}\rangle \mid \langle v_{i},v_{j}\rangle \epsilon V(G)\rbrace

die Kantenmenge bezeichent.

Eine Kante $e_{i,j}\epsilon E(G)$ besitzt die Wichtung $w_{i,j}{\mathrel {\widehat {=}}}w(e_{i,j})\epsilon R^{+}.$

Zum Verständnis ein Beispiel:

Hier handelt es sich um einen gerichteten Graphen.

Knoten: $V(G)=\lbrace v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\rbrace$

Kanten: $E(G)=\lbrace e_{12},e_{14},e_{23},e_{25},e_{26},e_{36},e_{45},e_{56}\rbrace$

Wichtungen: $W(E)=\lbrace w_{12}=20,w_{14}=39,w_{23}=14,w_{25}=27,w_{26}=70,w_{36}=19,w_{45}=17,w_{56}=45\rbrace$

Wichtige Begriffe der Graphentheorie:

inzident = wenn $v\epsilon e$

benachbart (adjazent) = wenn $v_{1}v_{2}\epsilon E(G)$ oder wenn 2 Kanten denselben Knoten haben

vollständig = sind je zwei Knoten von G benachbart, so heißt G vollständig

Hier soll nicht weiter in die Mathematik der Graphentheorie eingangen werden, da dies für den Dijkstra-Algorithmus nicht notwendig ist. Falls Intersse besteht, mehr über die Graphentheorie zu erfahren, empfehle ich das Buch „Graphentheorie3“ von Reinhard Diestel. Dieses Buch liegt zum kostenlosen Download bereit unter:

http://www.math.uni-hamburg.de/home/diestel/books/graphentheorie/GraphentheorieIII.counted.pdf

Kürzeste Wege

Um den kürzesten Weg eines Startpunktes zu einem beliebigen Knoten eines Gaphen zu benennen, gibt es mehrere Möglichkeiten:

- durch den Kantenzug: $\langle e_{ab},e_{bc},...,e_{yz}\rangle$ ( $e_{ab}$ bezeichnet die Kante von Knoten a nach Knoten b)

- durch die durchlaufenen Knoten: $\langle v_{a},v_{b},v_{c},...,v_{z}\rangle$ ( $v_{a}$ bezeichnet den Knoten a)

- durch die Wichtungen: $\langle w_{ab}+w_{bc}+...+w_{yz}=min\rangle$ ( $w_{ab}$ bezeichnet den Wert der Kante von Knoten a nach Knoten b)

Für jeden Knoten eines Graphen gibt es immer nur einen kürzesten Weg, es sei denn es gibt einen gleich großen Weg, dann existieren für diesen Knoten zwei Kantenzüge. Für einen beliebigen Knoten v auf einem Kantenzug ist dieser Kantenzug die kürzeste Verbindung vom Startknoten aus gesehen zum Knoten v. Man nennt einen beliebigen Knoten f "Vorgänger", wenn auf demselben Kantenzug ein weiterer Knoten g folgt. So ist Knoten f der Vorgänger von Knoten g. Das heißt, man kann den kürzesten Weg mit Hilfe des Vorgängers beschreiben.

Dijkstra-Algorithmus

Dieser Algorithmus berechnet die kürzesten Wege eines Graphen von einem Startknoten aus. Wie in Punkt "kürzeste Wege" schon genannt, kann der kürzeste Weg mit Hilfe des Vorgängers bestimmt werden. Damit der Algorithmus funktionieren kann, dürfen die Gewichtungen der Kanten nicht negativ sein.

Vorgehensweise

1. Initialisiere den Startknoten mit 0 und alle anderen Knoten mit ∞. Weise den Nachbarknoten die Eigenschaften Distanz (dist) und Vorgänger (pre) zu.

2. Suche den benachbarten Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange. (aus Front)

3. Speichere, dass dieser Knoten besucht wurde.

4. Berechne für alle neuen Nachbarknoten die Distanz zum Startpunkt.

4.1 Der Knoten ist „neu“ und hat keinen Vorgänger: Die Werte werden gespeichert.

4.2 Der Knoten ist schon bekannt und hat somit einen Vorgänger:

2 Möglichkeiten:

- Der aktuelle Weg ist länger: Werte bleiben erhalten

- Der aktuelle Weg ist kürzer: Werte werden überschrieben

Beispiel

Hier wird der Startknoten (a) mit dem Wert 0 initialisiert.

Den Nachbarknoten (b, d) werden ihre Werte (20, 9) und ihr Vorgänger (a) zugewiesen. Außerdem werden die "neuen" Knoten (b, d) in der Front abgespeichert.

Es wurde der Knoten aus der Front entnommen, der den kleinsten Wert besitzt (d=9). Nun werden von diesem Knoten die Nachbarknoten bestimmt (e). Außerdem wird der Knoten d aus der Front gelöscht und der "neue" Knoten (e) in der Front gespeichert. Dem Knoten e wird der Wert 35 zugeordnet. Dies entspricht der Wertung von Knoten d plus dem Wert der hinführenden Kante. Wie immer wird auch bei diesem Knoten der Vorgänger gespeichert (d).

Der Knoten mit dem kleinsten Wert (b=20) wurde aus der Front entnommen und daraus gelöscht. Von diesem Knoten aus werden die Nachbarknoten (c, e, f) bestimmt und ihre Werte zugewiesen. Da der neue Wert für den Knoten e größer ist als der alte, bleiben die Werte in Knoten e erhalten und die Kante von b nach e ist nicht mehr relevant für die kürzeste Strecke. Da die Knoten c und f vorher noch nicht bekannt waren, werden sie in der Front gespeichert. Momentan sind die Knoten e=35, c=35 und f =90 in der Front.

Da jetzt zwei Knoten in der Front dieselbe Wertung haben, ist es Zufall oder besser gesagt programmierungsabhängig, welcher Knoten nun betrachtet wird. Hier ist es Knoten e. Dieser wird aus der Front gelöscht. Der einzige Nachbarknoten ist Punkt f. Da dieser schon einen Wert besitzt (90) und der neue Wert (35 + 40 = 75) kleiner ist, ist die Kante von b nach f nicht mehr von Bedeutung und es werden die neuen Daten (Wert, Vorgänger) gespeichert.

Der nächste Knoten aus der Front ist Knoten c. Es werden wieder die Nachbarknoten (f) bestimmt und überprüft, ob der Knoten schon bekannt ist. Da er schon bekannt ist, wird überprüft, ob der neue Wert gößer oder kleiner ist. Der Wert ist hier kleiner, somit werden die Eigenschaften des Knoten f gelöscht und neu initialisiert. Der Knoten f hat keine Kanten, die von ihm wegführen, somit ist der Graph berechnet, die Front leer und wir kennen von jedem Knoten den geringsten Abstand zum Startknoten, seinen Vorgänger und dadurch den kürzesten Weg.

Somit ergeben sich zwei Kantenzüge. Von Knoten a bis f über b und c mit einer Gesamtlänge von 60, sowie von a bis e über d mit der Gesamtlänge von 35.

Trace-Tabelle

Eine Trace-Tabelle stellt den Rechenverlauf des Dijkstra Algorithmus tabellarisch dar. Durch diese Darstellung erhält man am Ende des Algorithmus alle kürzesten Wege vom Startpunkt aus gesehen auf alle anderen Punkte des Graphen.

Hierzu ein Beispiel:

Dies ist derselbe Graph wie oben.

Will man diesen Graphen berechnen, erstellt man am besten eine Tabelle, die sogenannte Trace-Tabelle. In der ersten Spalte schreibt man alle Knoten untereinander. Pro Durchlauf braucht man je drei weitere Spalten. In der ersten Spalte steht immer der Vorgänger, der den kürzesten Weg zum Startpunkt hat, in der zweiten Spalte steht der kürzeste Abstand zum Startpunkt und in der dritten Spalte sieht man welche Knoten man schon besucht hat, oder welcher gerade "aktiv" ist (der in der Klammer). Bei dem Knoten f kann man schön sehen, dass der Wert und der Vorgänger oft wechseln. Je nachdem von welchem Punkt man gerade ausgeht. Am Ende (6.Durchlauf) sind alle Knoten abgearbeitet. Dies heißt, dass von jedem Knoten der entgültige Vorgänger und die kürzeste Strecke ermittelt wurde.

Nachdem man die Tabelle fertiggestellt hat, kann man seine Ergebnisse in eine weitere Tabelle eintragen. In der ersten Spalte stehen wieder die Knoten, in der zweiten der kürzeste Weg, ausgedrückt mit Hilfe der Vorgänger, und in der dritten Spalte der kürzeste Weg, ausgedrückt mit Hilfe der Strecke. Ein Beispiel: Der Knoten f hat im 6. Durchlauf den Knoten c als Vorgänger, der Knoten c hat den Knoten b als Vorgänger und der wiederrum den Knoten a. So entsteht die Kette a-b-c-f. Den Wert kann man in der letzten Spalte des 6. Durchlaufs ablesen.

Beispiel zum selbst rechnen

Ich möchte hier darauf hinweisen, dass es im Internet zahllose JAVA-Programme gibt, die den Dijkstra Algorithmus Schritt für Schritt anwenden. Sie dienen sehr gut dazu den Dijkstra Algorithmus nachzuvollziehen und zu verstehen, da diese die Rechenschritte schön veranschaulichen. Die Aufgaben und die dazugehörigen Lösungen wurden mit so einem Programm erstellt, somit dienen diese Aufgaben entweder zum Üben oder zum Nachvollziehen dieser Thematik. Solche Programme stehen kostenfrei im Internet zu Verfügung. Unter der Rubrik "Links" sind Beispiele für solche Programme verlinkt. Ich empfehle den dijkstravis.

Aufgabe 1: Diese Aufgabe könnte man auch ohne Dijkstra-Algorithmus im Handumdrehen lösen. Sie dient zum einfachen Üben oder zum Nachvollziehen, da die Lösung hierzu Schritt für Schritt erklärt wird.

Finde den kürzesten Weg von Karlsruhe nach Mannheim.

Aufgabe 2: An sich unterscheidet sich diese Aufgabe von der obigen nur darin, dass sie aus mehr Knoten und Kanten besteht. Durch den Dijkstra-Algorithmus sollte diese Aufgabe kein Problem sein, eher zeitaufwendig. :)

Finde den kürzesten Weg von Karlsruhe nach Hamburg.

Hier gehts zu den Lösungen.

Links

http://sourceforge.net/projects/dijkstromania/

http://mac.softpedia.com/get/Utilities/DijkstraVis.shtml

http://www-m9.ma.tum.de/Allgemeines/DijkstraApplet