Kürzeste Wege nach Dijkstra

Freitag, 10. April 2009 um 09:04 Uhr
Drucken

Der Algorithmus der kürzesten Wege nach Dijkstra läßt sich zum Beispiel am Verkehrsnetz der Bahn verdeutlichen. Die einzelnen Orte werden durch Verkehrsstrecken miteinander verbunden, aber nicht jeder Weg ist der kürzeste. Dieses Problem ist zum Beispiel auch für andere Routenplaner interessant. Eine Lösung ist der nach Dijkstra benannte Algorithmus. Zur Verdeutlichung sei ein Netz von Wikipedia gegeben.

 

Das Prinzip des Durchgehens basiert auf folgender Schrittfolge.

.....

setze alle Knoten auf eine unendliche Entfernung, den Startknoten s auf die Entfernung 0 - suche alle erreichbaren Knoten heraus und notiere ihre Distanz vom Startknoten, setze dann den Startknoten auf erledigt - suche den Knoten mit der kürzesten Verbindung zu s heraus, von dort führt der Weg auf die gleiche Art weiter, wobei immer die Gesamtdistanz zum Startknoten s relevant ist.

sollte vom Startknoten aus eine kürzere Distanz als die vorhandene entstehen, so wird diese als neuer Weg markiert und der alte Wert überschrieben, sollte der entgegengesetzte Fall auftreten, wird der Weg nicht beachtet

......

Für obiges Beispiel ergäbe sich folgendes Bild, die Städte seien abgekürzt (x) bedeutet erledigt, (oo) unendlich

F M W S Karl
E
N Ka A M
F
x 85 217 oo oo oo oo 173 oo oo
F , M
x x 217 oo 165 oo oo 173 oo oo
F , M , Karl x x 217 oo x oo oo 173 oo oo
F , M , Karl , Ka x x 217 oo x oo oo x 415 675
F , M , Karl , Ka ,W x x x oo x 403 320 x 415 487
F , M , Karl , Ka ,W , N x x x 503 x 403 x x 415 487
F , M , Karl , Ka ,W , N , E
x x x 503 x x x x 415 487


..... A , M , S

Implementierung des Dijkstra Algorithmus in Python

Aktualisiert ( Freitag, 01. Januar 2010 um 20:27 Uhr )