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.
Klausur 02.08.12 Algorithmus von Dijkstra
Hallo, ich bin etwas verwirrt. Man sollte in der Aufgabe 3a den kürzesten Weg vom Knoten 1 zu allen anderen Knoten in einem Graph finden.
Also ich nehme mal den Knoten 1 und schau auf den kleinsten Wert, das ist 5 zu dem Knoten 3. Ich wähle den Knoten 3: 1 → 3
Nun soll ich weiter laufen. Laut des Algorithmus muss ich wieder den kleinsten Wert nehmen, ist ja der Knoten 5 mit dem Wert 8.
5+8=13… Aber es ist nicht der kürzeste Pfad zu dem Knoten 5. Zum Beispiel 1-4-5 kostet 9+3=12… Jetzt kommt die Frage, was soll ich denn in der Tabelle schreiben, im quasi 3. Zeile (1.Zeile ist gegeben, 2.Zeile: 0 15 ‘5’ 9 infinity). Muss ich sowas schreiben: 0 9 5 10 8.
- Weiter muss ich den nächsten Nachfolger vom Knoten 3 nehmen (Knoten 5), aber es ist ja falscher Pfad…
Danke.
Dein Startknoten ist 1 von 1 kannst du die Knoten 2,3,4 mit den Gewichten 15,5,9 erreichen. Die Gewichte sind kleiner als unendlich also aktualisierst du die Distanz(=Gewicht) der Knoten 2,3,4 und hast dann eine Tabellezeile:
0 | 15 | 5 | 9 | -1
(-1 soll unendlich darstellen)
Daraus wählst du jetzt wieder den Knoten mit dem geringsten Gewicht den du noch nicht besucht hast aus. Das ist die 3, da sieht dann die nächste Zeile so aus:
0 | 5+9=14 | 5 | 9 | 5+8=13
Das ganze machst solange weiter bis du alle erreichbaren Knoten besucht hast. Hoffe das hilft 
Wenn nicht gibts ja auch noch wiki
dankeschön, ich hab meinen Denkfehler mit deiner 2. Zeile verstanden.