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 24.07.2014 Aufgabe 3d)
Eine Frage, in der Loesungstabelle: wenn kein alter Pfad bekannt ist, und es zwischen zwei Knoten (v,n) es keine direkte verbindung gibt, wird dann unendlich eingetragen?
D A B 7 |5|
D A C ∞ |13| <------
A B C 11 |7|
D B C 13 |11|
Also bei D nach C gibt es ja keine kante, hoechstens ueber D → B → C
Wuerde man daher hier unendlich eintragen? wenn noch kein “alter” Pfad bekannt ist?
und WENN es eine direkte Kante gaebe, so ware diese der “alte” wert?
Richtig, wie auch in der obersten Zeile der Tabelle steht, ist die alte Länge nur die Kante von v nach n. Der Algorithmus von Floyd berechnet ja erst unter anderem, ob es einen noch kürzeren Pfad von v nach n gibt. Wenn also noch keine Kante zwischen v und n existiert ist die alte Länge unendlich. Wenn du dann im weiteren Verlauf erneut dasselbe v und n hast, nimmst du dann logischerweise die zuletzt berechnete Länge.
PS: In deiner letzten Zeile ist noch ein Fehler (Lösung)
D A B 7 |5|
D A C ∞ |13|
A B C 11 |7|
D B C 13 |9|
stimmt, D,B gibt es ja schon nen kuerzeren…Oh man…
Jetzt ists richtig^^