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 Algo von Floyd
Hallo,
ich hab gerade versucht, die Tabelle aus der letzten Klausur nach dem Algo von Floyd auszufüllen.
Jedoch habe ich gar keine Anhaltspunkte, wie das funktionieren soll, denn weder in den Vorlesungsfolien noch im Internet habe ich Bspiele gefunden.
Vielen Dank!
https://www2.cs.fau.de/teaching/WS2012/AuD/slides/secure/aud-14.pdf
http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
In Introduction to Alogrithms von Cormen sollte es auch drin sein.
Das alles sagt mir aber nichts 
Du hast also im Wikipedia-Artikel links auf “Deutsch” geklickt, und selbst dort nichts verstanden?
Hier die ausgefüllte Floyd-Tabelle aus der Klausur, wie es meiner Meinung nach aussehen müsste.
Mit rot habe ich jeweils das Minimum gekennzeichnet.
Hoffe, ich konnte dir ein bisschen helfen 
Attachment:
Floyd.jpg: https://fsi.cs.fau.de/unb-attachments/post_117441/Floyd.jpg
1 „Gefällt mir“
Vielen lieben Dank
Uploaded with ImageShack.us
Sieht der Graph am Ende so aus? Es fehlt nur die Kante von 4 nach 3 mit Länge 10…Kann das sein?
Und noch eine Frage: Bei Knoten 3 ist der Vorgänger 1 und Nachfolger 5. Die neue Länge ist 13 und die alte ist 18. Aber die alte Länge hätte auch 11 sein können, wenn ich über Knoten 4 laufen würde. Wie enscheidet man bei so einem Fall, welchen Pfad man nimmt? Nimmt man den längeren? Oder läuft man hier über 2, weil dieser schon bearbeitet wurde?
Danke schonmal :)))
Uploaded with ImageShack.us
Hallöchen,
mir bereitet die Implementierung von Floyd noch ein paar Probleme. Ich versteh diese 3fach geschachtelte Schleife nicht… Vorallem diesen Vergleich.
Ich weiss, dass die erste schleife für den Knoten selber, die zweite für den Vorgänger und die dritte für den Nachfolger steht. Kann mir jemand helfen?
Ich habe die Implementierung aus der Vorlesung komplett übernommen und mir diese Mainmethode geschrieben.
Danke
Code als Screenshot ist nicht schoen. Nimm nimmer code-tags.
Der Vergleich in der Schleife fragt ab, ob der Pfad ueber den “Umweg”-Knoten i billiger ist als direkt von j nach k.
Trotzdem:
if (g[j][i] + g[i][k] < g[j][k])Da schaust du, ob die Summe der Wegkosten von Knoten j nach i und von i weiter nach k kleiner ist, als die momentan für den Weg von j nach k gespeicherten Kosten. Wenn’s über Knoten i schneller geht, dann aktualisierst du die Kosten anschließend.
Die Schleifen sind dann einfach dazu da, alle Wegkombinationen systematisch durchzutesten, sodass am Ende zwischen allen Knotenpaaren die geringsten Kosten stehen.
So und nun eine Frage von mir: Was bringt einen dazu, seinen Code vom Bildschirm abzufotografieren, das Bild irgendwo hochzuladen, nur um dann das Foto im Forum zu verlinken, wenn es auch Ctrl+C und Ctrl+V getan hätte??? 
Tut mir echt leid leute…ich lerne seit über 10 Stunden, mein Kopf ist tot
Deshalb sorry für die ganze gaga und danke für die antworten
Ich wurde gut unterhalten 
Aber primär von Wikipedia:
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
temp = dist[i][k] + dist[k][j] // This will optimize the code performance , by removing the redundant expression .
if temp < dist[i][j] then // Redundant code here may be like using dist[i][k] + dist[k][j] instead of using temp .
dist[i][j] ← tempGenious at work! 
Mach ne Pause und dreh eine Runde um den Block. Hilft ungemein beim Kopf freikriegen. 
2 „Gefällt mir“
Hallo
habe auch den Code aus der Vorlesung übernommen und iwie hat er nur nach einer kleiner Änderung funktioniert. Poste dir nochmal hier meinen Code, vll. hilft dir das weiter
public class Floyd {
public static double[][] floyd(double [][] cost){
int n = cost.length;
double [][] g = new double[n][n];
for(int j = 0; j<n; j++){
for(int k = 0; k<n; k++){
g[j][k] = cost[j][k];
}
}
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
for(int k = 0; k<n; k++){
double d = g[i][k] + g[k][j];
if( d < g[i][j]){
g[i][j] = d;
}
}
}
}
return g;
}
1 „Gefällt mir“
Hallo
vom Knoten 1 zum Knoten 5 kannst du ja entweder über 2, 3 oder 4 als Zwischenknoten kommen.
1 - 2 - 5: 18
1 - 3 - 5: 13
1 - 4 - 5: 12
Du updatest ja deine Liste, also am Schluss ist der Weg 1 - 4 - 5 mit 12 am günstigsten und somit wählst du den aus.
Hoffe, dir hilft das ein bisschen weiter, wenn nicht, frag einfach noch was dir unklar ist und hoffentlich kann ich dir dann mit meinen Antworten helfen
1 „Gefällt mir“
Vielen Dank Ina89 Die Implementierung habe ich jetzt verstanden.
Bei der neuen Länge nehme ich die 12, weil sie am kürzesten ist, aber meine Frage war eigtl. auf die alte Länge bezogen.
Wenn ich 1-3-5 mache, ist die neue Länge 13, die alte ist 18 ( weil man über Knoten 2 läuft). Man könnte aber auch über Knoten 4 laufen, und hätte damit nur die Länge 11. Warum hast du bei deiner Lösung trotzdem die 18 genommen?
Bin mir nicht sicher, ob ich deine Frage richtig verstanden habe, aber hier nochmal wie ich vorgehe.
Im ersten Schritt sollte man sich laut Tabelle den Knoten 2 anschauen, der 3 Vorgänger und einen Nachfolger hat.
Die Kante 1 - 5 gab es davor noch nicht, deshalb ist die alte Länge unendlich und die neue Länge durch Knoten 2 mit 18 günstiger.
Wenn man sich den Knoten 3 anschaut, kann man von 1 durch 3 zur 5 laufen. 1 - 3 - 5 ist mit 13 günstiger als die alte Länge 18.
Nun schaut man sich Knoten 4 an. Für 1 - 4 - 5 ergibt sich 12, was günstiger ist als 13. Da es keine weiteren Zwischenknoten mehr gibt und 12 von alle am günstigsten war, bleibt es dabei.
Du musst dir das wie ne Liste vorstellen, die du updatest, falls man einen günstigeren Weg gefunden hat. Falls nicht, bleibt die alte Länge. Wenn du 1 - 3 - 5 berechnest, weißt du ja noch nicht, dass du über 1 - 4 - 5 einen günstigeren Weg finden wirst.
Deutlicher jetzt? 