Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Dijkstra
irgendwie hab ich mir jetzt gerade nen Knoten in den Kopf gedacht… :rolleyes:
Ich nehm doch immer zunächst den Knoten mit dem kürzesten Pfad in die Lösung auf und speichere ALLE Nachfolger (auch von nicht hinzugenommenen Knoten) in meiner queue, oder? Oder werden in der queue immer nur die Nachfolger des aktuellen Knoten gespeichert?
Bsp Klausur 19.Sept 2005 Aufgabe 6 - die Tabellle wird ganz schön kurz :vogel: :
Knoten s a b c d e f z Warteschlange
Kosten 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ a,b
Schritt 1 3 5 ∞ ∞ ∞ ∞ ∞ c,d,f
2 13 8 ∞ 20 ∞ f
3 ∞ 10 ∞ e,z
4 13 12
=> kürzester Pfad von s nach z: s-b-d-f-z
Kann jemand die Tabelle bestätigen??? Die Logik ist zwar sau einfach, aber die Tabelle verwirrt mich…
also ich hab mir jetz das nich so genau durchdacht, von dir. Aber über wikipedia hab ich n recht cooles java applet gefunden, wo man jeden graph selber schustern kann:
http://carbon.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html
alternativ gibts noch
http://www.gik.uni-karlsruhe.de/766.html
da kann man sich die funktion vom dijkstra an zwei vorgegebenen graphen anschaun.
ps: credits für den zweiten link @ guanta g 