Dijkstra Algorithmus: Unterschied zwischen den Versionen

Version vom 5. Februar 2008, 11:58 Uhr

Grundlegendes Konzept

Ein typisches Problem der Graphentheorie ist die Berechnung des kürzesten Weges in einem Graphen. Gesucht ist der optimale (kürzeste, günstigste) Weg von einem festgelegten Startknoten zu einem Endknoten. Der Dijkstra Algorithmus (benannt nach Edsger Wybe Dijkstra) ist eine Möglichkeit diese Problemstellung zu lösen.
Die Idee von Dijkstra besteht darin, dass man jeweils den Abstand des jeweiligen Nachbarknotens zum Startknoten mit einem Umweg über den Basisknoten vergleicht, und im folgenden jeweils nur noch den kürzeren Weg beachtet.

Erläuterung am Beispiel

Die genaue Vorgehensweise des Algorithmus wollen wir am folgenden Beispiel zeigen:

Der Startknoten ist mit dem Buchstaben A gekennzeichnet, der Endknoten mit E. Die Zahlen an den Kanten geben die Entfernungen der jeweiligen Knoten voneinander an. Den Startknoten definieren wir als ersten Basisknoten, von dem aus die Entfernungen zu den direkten Nachbarknoten berechnet werden. Die Entfernung zum Knoten B beträgt 3 LE (LE = Längeneinheiten) und zum Knoten C 5 LE. Es ist ebenfalls ersichtlich, dass die Knoten D und E auf keinem direkten Weg von A erreicht werden können. Mathematisch wird dies oft dadurch ausgedrückt, dass man die Entfernung als unendlich angibt.

Als nächsten Basisknoten wählt man nun den Knoten, der den kürzesten Abstand zum Startknoten hat. Der zweite Basisknoten ist somit Knoten B. Im folgenden Schritt werden nun die Entfernungen von Knoten B zu allen direkten Nachbarknoten, die noch nicht Basisknoten waren, berechnet, und zum Gesamtabstand des Startknotens hinzuaddiert. Knoten D ist also 3+7 = 10 LE von A entfernt, falls man den Weg A->B->D beschreiten würde. Der Abstand von Knoten E beträgt 8+3 = 11 LE, und der Abstand von Knoten C über den Umweg B beträgt 3+1 = 4 LE. Hier wird deutlich, dass man den Knoten C vom Startknoten aus schneller erreichen kann, wenn man den „Umweg“ über B geht, als wenn man den direkten Weg nehmen würde. Somit wird der alte Weg verworfen und der neue eingetragen. Wichtig dabei ist, dass man immer den direkten Vorgängerknoten notiert, in diesem Falle würde man also 4 B schreiben (4 LE mit dem Vorgängerknoten B).

Sind alle Wege über den Basisknoten B bestimmt, muss man einen neuen Basisknoten wählen. Der Knoten C ist der Knoten, der den nächst kürzesten Abstand vom Startknoten hat und wird somit zum 3. Basisknoten. Von ihm ausgehend werden wiederum die Abstände zu den benachbarten Knoten bestimmt und der Gesamtweg vom Startknoten berechnet. Findet man über den „Umweg“ über C einen kürzeren Weg, als vorher bekannt, wird dieser durch den neuen ersetzt. Man erkennt sofort, dass der Weg zum Zielknoten E über C 9 LE beträgt, und man somit 2 LE gegenüber dem Weg über B einsparen kann. Des Weiteren verkürzt sich der Weg zu Knoten D von 10 auf 6 LE.

Sobald nun alle Entfernungen von Knoten C bestimmt sind, wählt man den nächsten Basisknoten mit dem nächst kürzesten Abstand zum Startknoten. Die Wahl fällt damit auf Knoten D. Es werden, wie auch schon bei den vorherigen Schritten, jeweils die Entfernungen zu den Nachbarknoten bestimmt und der Weg durch den Neuen ersetzt, falls dieser kürzer ist. Der Zielknoten E ist mit dem Vorgänger D in 6+2 = 8 Längeneinheiten zu erreichen, dies ist nochmals kürzer als der Weg über Vorgänger C, der 9 LE betrug.

Im nächsten Schritt wird der Zielknoten E zum Basisknoten und somit ist das Ende des Dijkstra-Algorithmus erreicht. Das optimale Ergebnis kann man nun in der letzten Zeile der folgenden Tabelle ablesen:

Der kürzeste Weg ergibt sich also zu A--> B--> C--> D--> E und beträgt 8 Längeneinheiten.

Zusammenfassung

Abschließend wollen wir die Schritte des Dijkstra-Algorithmus noch einmal kurz darstellen:

1. Wahl des Ausgangsknotens als Basisknoten
2. Berechnung der gesamten Weglänge (Abstand vom Startknoten) zu allen Nachbarknoten des Basisknotens, die noch nicht Basisknoten waren. Ist der Weg kürzer als der bisher beste, so wird der neue Weg eingetragen.
3. Wahl des Knotens als Basisknoten, der unter den Knoten, die noch nicht Basisknoten gewesen sind, dem Startknoten am nächsten ist. Ist dieser Knoten der Zielknoten dann ist die Rechnung beendet (Basisknoten = Zielknoten). Andernfalls Fortsetzung mit Schritt 2.

Flash Animation

Wenn Sie sich eingehender mit dem Dijkstra-Algorithmus auseinandersetzen wollen, könnn Sie dies anhand einer Flash Animation der Universität Stuttgart oder anhand eines Tutorials der University of Melbourne.

Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Wintersemester 2007/2008

Vorlesungsmitschnitt zum Thema Dijkstra-Algorithmus aus dem Wintersemester 2007/2008

Wintersemester 2006/2007

Vorlesungsmitschnitt zum Thema Dijkstra-Algorithmus vom 31.10.2006 (Download)

Achtung: die Dateien aus dem WS 06/07 können fehlerhaft sein!
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.