Dijkstra Algorithmus - die 2te
-
Mir ist klar wie man die Mengen A, B, C, I, II, III konstruieren muss, jedoch frage ich mich wie ich anhand der Mengen die kürzerste Kantenfolge bestimmen soll - das kann man nicht einfach irgendwie ablesen - oder? dazu muss ich dann wieder ein breiten bzw. tiefensuche in den kanten der menge I durchführen und mir den Weg merken oder?
PS: Der Dijkstra Algo ist hier zu finden:
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D196288&p=274
-
Klar, das kann man nicht direkt erkennen. Die Mengen sind nur dazu da, daß es schneller geht. Die eine Menge kennt man ja schon => braucht man nicht mehr anschaun. Die dritte Menge erreicht man momentan noch nicht und die Mittlere ist die eigentlich interessante. Nur die muß man sich anschaun. Vielleicht kann man die aber auch irgendwie sortiert halten und so schnell rausfinden welcher Knoten der nächste sein muß. Dann muß man sich halt ein paar Gedanken machen, wie man das Updaten dieser Menge effizient hinkriegt.