vorige nächste Programm

Der Algorithmus von Dijkstra


Ein Algorithmus sehr ähnlicher Konzeption,der Algorithmus von Dijkstra, löst das Problem des kürzesten Weges: Im Beispiel werden die kürzesten Wege vom Knoten 1 zu alle anderen Knoten gesucht. Auch dieser Algorithmus arbeitet damit, dass zum Expansionsgraphen (hier: kW-Graph für kürzeste Wege) die nächstliegende Ecke ausgesucht wird, die keinen Zyklus erzeugt. Der Problemgraph wird so schichtenweise expandiert. Graph zu Dijkstra

Der entscheidende Unterschied zum Algorithmus von Prim ist aber die Prozedur verkürze, mit der für alle Vorgängerknoten -sie werden daher in einer eigenen Variablen gehalten- untersucht wird, ob durch den hinzugefügten Knoten ein kürzerer Weg zu ihnen möglich wird. In dem Fall wird der bisherige Weg durch den neuen ersetzt. Die Wege werden in dem von Turau vorgeschlagenen Programm nicht direkt geführt, sondern können rekursiv aus dem Array bestimmt werden. Hierin liegt deshalb ein besonderer Unterschied zum Algorithmus von Prim vor, als dadurch Entscheidungen vorheriger Schritte wieder rückgängig gemacht werden, was beim Algorithmus von Prim nicht passiert.

Das Turau vorgegebene Pascal - Programm liegt auch in einer Scheme - Version vor. Dabei habe ich mich aber sehr eng an die Vorgabe aus dem Pascal - Programm gehalten. Das Programm ist also nicht im funktionalen Stil geschrieben, sondern prozedural. Natürlich kann man das machen. Wenn man einen Kurs mit Scheme macht, sollte das aber eher die Ausnahme bleiben und nicht die Regel.

Als Datenstrukturen habe ich im Scheme - Programm die den ARRAYS entsprechenden VECTOR - Variablen gewählt. Die Zugriffe sind bis auf die Indizierung selbsterklärend -sonst siehe Scheme - Hilfe im R5RS. Beim Index muss man darauf achten. dass die Benennungen der Knoten bei 1 beginnen, die Indizes der vector - Variablen aber bei 0. Deshalb die immer wieder auftretende sub1 - Funktion.

Tabelle zu Dijkstra
Tabelle aus dem Text von Turau