Dijkstra Algorithmus

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:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1 Graph mit Knoten und Entfernungen

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:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: tabellarische Darstellung

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/Lecture

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

Dijkstra-Algorithmus (English)

Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.

Fundamental Concept

A typical problem of graph theory is shortest path calculation. The most optimal (shortest, cheapest) way to connect a predetermined start and end node is searched. Dijkstra algorithm (named after Edsger Wybe Dijkstra) is a possibility to solve this problem. The main idea of Dijkstra is comparing the distance of the immediate path between start node and neighbor node to the distance of the alternative path including a detour via the base node. In the following the longer path is neglected and the shorter one regarded.

Exemplification

The accurate procedure is demonstrated by the following example:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1 Graph mit Knoten und Entfernungen

The start node is defined as A while the end node gets designation E. The numbers on the edges declare the distances between the respective nodes. Firstly we define start node A as our base node, from which we calculate the distances to all directly neighboring nodes. The distance to node B is 5 LU (length unit) and to node C 5LU. Apparently node D and node E may not be achieved directly. This is mathematically expressed by declaring the distance as infinite.

The next base node is chosen by the criteria of having the shortest distance to the start node. Thus the next base node is node B. In the following step all distances from node B to neighboring nodes, which have not yet been a base node, are calculated and added to the total distance to the start node. The distance from A to D is 3+7=10LU by using the path A->B->D. Via detour the distance between A and E reduces to a total of 8+3=11LU and for node C 3+1=4LU. It becomes clear that the path from A to C including a detour via B is shorter than the direct way. It is important to note always the predecessor node in this case 4 B (predecessor node B with a total distance of 4 LU).

If all paths via base node B are identified, a new base node will be determined. The next shortest distance to the start node offers node C, thus we choose C as new base node. Starting with node C we have to diagnose all distances to neighboring nodes and furthermore calculate the total distances to the start node. If a detour via node C delivers a shorter distance than the previously known one, will the old path one replaced by the new path via C. It is immediately clear that the path to end node E via node C has a total distance of 9 LU and thus a distance of 2 LU may be reduced in contrast to the path via node B. Furthermore the distance to node D reduces from 10 to 6 LU, too.

As soon as all distances from node C are determined, the next base node, which has the shortest distance to start node A, will be chosen. Thus node D becomes new base node. Analogous to previous steps all distances from node D to neighboring nodes will be determined and replaced if being shorter than the previous path. The goal node may be achieved via predecessor node D with a distance of 6+2 = 8 LU. This distance is shorter than the previous path via predecessor C having a distance of 9LU.

In the next step goal node E becomes base node, which means the ending of Dijkstra-Algorithm. The optimal solution can be seen in the last line of the following table.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: tabellarische Darstellung

The path A--> B--> C--> D--> E is the shortest one with a total distance of 8 length units.

Summary

Finally we want to demonstrate briefly a step-by-step approach of Dijkstra-Algorithm.

1. Selection of the initial node as base node
2. Calculation of path length (distance to initial node) to all neighboring nodes, which have not yet been base node. If the new path is shorter, the older one will be replaced.
3. Determination of the next base node, which has to have the shortest distance to the start node, without being base node before. If goal node becomes base node the Dijkstra-Algorithm will be stopped (base node=goal node). Otherwise continue with step 2.

Flash Animation

To deepen the understanding of Dijkstra-Algorithm you may have a look on following links: Flash Animation der Universität Stuttgart Tutorials der University of Melbourne.

Lecture

A video lecture on the topic portrayed above is available.

Dijkstra-Algorithmus (English)

Please consider the following points to watch this lecture: Hinweise zum Betrachten