habe gerade den Dijkstra-Algorithmus implementiert und wollte euch den Code nicht vorenthalten.
Vielleicht interessiert sich ja jemand dafür.Habe bis auf die HeapArray-Klasse (Quelle siehe Javadoc), die ich jedoch ein bisschen umgeschrieben habe, alles selbst gemacht. Im Zip ist der Quellcode und ein lauffähiges Jar als Testprogramm.
Ich habe das Beispiel aus der Wikipedia ( http://de.wikipedia.org/wiki/Dijkstra-A ... s#Beispiel ) benutzt. Start- und Ziel-Ort kann man dem Programm als Parameter übergeben.
Bitte wundert euch nicht, wenn komische Umwege (Karlsruhe -> Augsburg -> Muenchen -> Nuernberg -> Stuttgart) vorgeschlagen werden, das ist zwar nicht realistisch, aber der kürzeste Weg in diesem Graph.
Es gibt einfach keine Straße von Karlsruhe nach Stuttgart.
Der Algorithmus ist 1:1 aus dem Algo-Buch übernommen. Es lassen sich auch weitere Algorithmen einfügen, falls jemand Lust hat.
Im Testprogramm kann man auch beliebige andere Graphen erstellen.
Einschränkungen:
- Die Graphen sind ungerichtet und Hin- und Rückweg sind gleich teuer.
- Es lassen sich keine Knoten/Kanten löschen, nachdem sie eingefügt wurden.
Auf Stil und Performance wurde auch nicht primär geachtet.
Edit: Anhang wegen PSE gelöscht.