Klausur 25.02.2010 Aufgabe 7b. Dijkstra

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 25.02.2010 Aufgabe 7b. Dijkstra
Bei der Aufgabe 7.b habe ich einmal folgende Lösung rausgebracht.
Gelb sind die zu markierenden Sterne.

A B C D E F G H
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
4 2 ∞ ∞ ∞ ∞ ∞
3 5 ∞ ∞ ∞ ∞
∞ 4 ∞ ∞
5 ∞ 8
10
9

als ich für G die 10 rausgebracht hab, musst ich ja nochmal ein paar Knoten zurück, muss ich dann die drittletzte Zeile nochmal hinschreiben und die 8 markieren oder kann ich gleich die letzte Zeile hinschreiben?
Und stimmt diese Lösung?

Würde mich sehr über eine Antwort freuen, da ich bis jetzt noch keine Lösung in dieser Art gesehen habe. (also die ganze Tabelle)


die ersten 2 Zeilen sehen ganz gut aus. Danach weiß ich nicht genau was du dir gedacht hast. Zum einen musst du in jeder Spalte einmal eine Zahl markiert haben am Ende (D und H fehlen) und wenn du G10 markierst, kann das nicht sein, denn eine markierte Zahl ist immer der kürzest mögliche Weg, aber es geht ja auch in 9). (Und von A->D brauch ich auch mehr als 5 :wink: )

Vllt erklärst du mal, wie du auf Z. 3 und 4 gekommen bist?

[...]musst ich ja nochmal ein paar Knoten zurück[...] ? was meinst du mit zurück?


Also als erstes geh ich ja von A nach B und C ist die dritte Zeile.
Dann wählt man doch den kleineren Wert also die 2.
Also muss ich jetzt alle Wege von C gehen, also von C zu D und zu B, wobei ich dann ja bereits einen kürzeren Weg(den zu B) gefunden habe.

Nun wieder den kleineren Weg weitergehen, also von B zu F, was die 4te Zeile sein soll.

Dann die Werte von F zu E und H, wieder kleineren Wert nehmen, also mit E weiter machen.
Dann von E zu G, weil zu D geht ja net, weils nur ein längerer Weg wäre, ergibt dann die 10.

Dann geh ich zurück zu F und von dort aus zu G und bekomm den letzten Wert die 9.
Aber iwas stimmt da nicht…


Sieht auf den ersten Blick eher nach Prim aus bei dir.

Schau das mal:
http://www.youtube.com/watch?v=8Ls1RqHCOPw


Der neue überarbeitete Versuch

A B C D E F G H
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
4 2 ∞ ∞ ∞ ∞ ∞
3 7 ∞ ∞ ∞ ∞
7 ∞ 4 ∞ ∞
7 5 ∞ 8
7 10 8
10 8
9

Könnte das jetzt so stimmen?


Ja, sieht besser aus!


Hab’s genauso :).

Wie ist das eig. mit den schon betrachteten (orange).
Soll man die Felder dananch leerlassen, einen senkrechten Strich machen, alles bis unten abschreiben oder einen senkrechten Strich bis zur vorletzen Zeile und dann in der letzten für alle ein Ergebnis hinschreiben?


Wenn unten Kästchen hingemalt sind, musst du sie ausfüllen, ansonsten kannst du das machen wie du willst. Nur alles hinschreiben ist ne schlechte Idee, das dauert unnötig lang und verwirrt beim Lesen.