Der Dijkstra-Algorithmus. Ein Algorithmus der Graphentheorie zur Lösung des Kürzesten-Wege-Problems

Inhaltsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

1 Einleitung

2 Begriffsbestimmung

3 Verfahrensbeschreibung

4 Graphisches Beispiel

5 Zusammenfassung und Ausblick

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Was ist der kürzeste Weg von Paderborn nach Duisburg? Wie besuche ich all meine Freunde, die im Ruhrgebiet an verschiedenen Orten wohnen, von Paderborn mit einer möglichst kurzen Rundreise?

Solche und viele andere Fragen lassen sich als Probleme in Graphen verfassen und sind durch sog. Graphenalgorithmen zu lösen.^[1]

In der vorliegenden Ausarbeitung wird der Dijkstra-Algorithmus aus der Graphentheorie vorgestellt. In Kapitel 2 erfolgt zunächst eine Begriffsbestimmung. Weiter wird in Kapitel 3 das Verfahren des Dijkstra-Algorithmus im Allgemeinen beschrieben. Schwerpunktmäßig behandelt die vorliegende Arbeit in Kapitel 4 die Erläuterung der Berechnung des Kürzesten-Wege-Problems m. H. des Dijkstra-Algorithmus. Dies erfolgt anhand eines graphischen Beispiels ausgehend vom Spezialfall eines einfachen, ungerichteten, nichtnegativ bewerteten Graphen.^[2] Abschließend erfolgt eine Zusammenfassung mit einem Ausblick weiterer Algorithmen.

2 Begriffsbestimmung

Der Dijkstra-Algorithmus, benannt nach seinem Erfinder Edsger Dijkstra, der diesen im Jahre 1959 veröffentlicht hat,^[3] ist ein Algorithmus aus der Graphentheorie, der das Kürzeste-Wege-Problem lösen kann.^[4] Mit diesem ist es möglich, kürzeste Entfernungen von einem Startknoten zu einem Zielknoten oder zu allen anderen Knoten zu finden.^[5] Der Dijkstra-Algorithmus zählt zu den sog. Greedy-Algorithmen, bei denen immer von derselben Situation ausgegangen wird: Es besteht ein Optimierungsproblem, für das eine optimale Lösung konstruiert werden soll.^[6] Jede Entscheidung wird lediglich einmal getroffen, und zwar für diejenige Möglichkeit, die auf Grundlage der gegebenen Informationen das beste Ergebnis zusichert, d. h. Greedy-Algorithmen versuchen gierig (engl. greedy) bei jeder Entscheidung den größtmöglichen Fortschritt zu erzielen.^[7]

3 Verfahrensbeschreibung

Gegeben sei ein ungerichteter, bewerteter Graph mit einer Knoten- und Kantenmenge. Eine Veranschaulichung eines solchen Graphen kann durch eine Vorstellung eines Netzes von verschiedenen Straßen zwischen Orten erfolgen. Die Knotenmenge stellt die Orte dar, wohingegen die Kanten zwischen den Orten die Straßen darstellen. Voraussetzung ist, dass jede einzelne Kante eine nichtnegative Länge hat.^[8] Alle kürzesten Wege, die von einem Anfangsknoten zu jedem beliebigen anderen Knoten ausgehen, sind gesucht.^[9] In jedem Durchgang wird der Knoten ausgewählt, der am nächsten zum Startknoten ist und noch nicht besucht worden ist.^[10] Hieraus folgt die Richtigkeit des Algorithmus, denn, wenn der kürzeste Weg zu diesem Knoten über einen anderen Knoten verlaufen würde, der noch nicht besucht worden ist, dann wäre dieser Knoten näher am Startknoten.^[11]

Wie der Dijkstra-Algorithmus dieses Problem konkret löst, wird im nachfolgenden Kapitel anhand der Abb. 1 erläutert.

4 Graphisches Beispiel

Die im Kapitel 3 beschriebene Vorstellung wird zunächst auf einen Graphen übertragen. Die Abb. 1 stellt die Übertragung der Vorstellung eines Netzes aus Orten und Straßen in einem Graphen dar.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1 : Entscheidungsbaum zum ersten und zweiten Schritt des Dijkstra-Algorithmus für einen Graphen mit n = 5 Knoten (Quelle: Arnold (2009): 58)

Die nachfolgende Beschreibung der Berechnung des Dijkstra-Algorithmus orientiert sich an der Darstellung nach Arnold und Furmans.^[12]

Orientiert an der Abb. 1 ist es Voraussetzung zunächst einen Basisknoten i als Startknoten festzulegen und die Wege cij zu allen Knoten j, die ausgehend vom Basisknoten i über einen einzigen Pfeil zu erreichen sind, zu bestimmen. Damit ergibt sich die erste Ebene (v = 1) in der Abb. 1, aus der der kleinste Wert aller Wege cij als erster kürzester Weg dik endgültig zu markieren ist. Es sei angenommen, dass der Weg c14 den kleinsten Wert hat, woraus sich dik = d14 = c14 ergibt. Der durch diesen Weg erreichte Knoten k wird zum nächsten Basisknoten (dem zweiten Basisknoten k) bestimmt, wo wieder die Wege ckj zu allen Nachbarknoten, die vom zweiten Basisknoten k aus jeweils mit lediglich einem Pfeil erreichbar sind, bestimmt werden. Hieraus ergibt sich nunmehr die zweite Ebene in der Abb. 1 (v = 2). Damit sind die Längen der neuen Gesamtwege dik (erster kürzester Weg) als einen kürzesten Teilweg und den neuen Teilwegen ckj berechnet, wobei sich jetzt die Frage stellt, ob sie kürzer als die bereits bekannten Wege cij sind. Konkret für das in der Abb. 1 dargestellte Bsp. lautet die Frage:

Abbildung in dieser Leseprobe nicht enthalten

Wenn sich ergibt, dass dik + ckj > cij ist, werden dazugehörige Äste des Entscheidungsbaums nicht weiter konstruiert, da somit die Wege ckj im Graphen keine kürzesten Teilwege darstellen können. Es sei angenommen, dass sich folgende Antwort auf die Frage ergibt:

[...]

^[1] Vgl. Ottmann, Widmayer (2012): 589.

^[2] Ein Graph besteht aus einer Knoten- und Kantenmenge. Sind die mit Kanten verbundenen Knotenpaare nicht geordnet, ist der Graph ungerichtet. Wenn sämtliche Kanten eine Bewertung haben, ist es ein bewerteter Graph. Vgl. Domschke, Drexl (2005): 65-68.

^[3] Vgl. Hußmann, Lutz-Westphal (2007): 31.

^[4] Vgl. Mahlmann, Schindelhauer (2007): 20.

^[5] Vgl. Domschke (1973): 127.

^[6] Vgl. Schöning (2001): 185f.

^[7] Vgl. Weicker (2013): 117.

^[8] Vgl. Cormen et. al. (2004): 593.

^[9] Vgl. Schöning (2001): 193.

^[10] Vgl. Mahlmann, Schindelhauer (2007): 20.

^[11] Vgl. Mahlmann, Schindelhauer (2007): 20.

^[12] Vgl. Arnold, Furmans (2009): 58f.