Floyd-Warshall-Algorithmus

[Hans W. (Gast)]

Hi Leute!

Ich frage mich schon die ganze Zeit ob es für den Floyd-Warshall 
Algorithmus eine einfachere Berechnungsmethode gibt. Wenn ich das so 
mache, wie ich das gelernt hab, braucht man da ja ewig für!

Bild hab ich euch angehängt!

Wenn ich nun bspw. in der neuen D^1 Matrix den Wert an der Stelle 2,1 
berechnen möchte, dann rechne ich:

2,1: 2,a + a,1 = 2,1 + 1,1 = 1+0 = 1 Das "a" ist die Potenz der neu zu 
berechnenden Matrix; hier also "1".

Nun vergleiche ich den errechnete neuen Wert mit dem Wert in der Matrix 
D^0. Ist der neue Wert kleiner als der alte Wert wird der neue an die 
Stelle 2,1 in der D^1 Matrix geschrieben. Ist der neue Wert größer als 
der alte Wert wird der alte Wert übernommen.

Das die Diagonale immer 0 ist, ist mir klar. Deswegen war nun auch 
dieses Beispiel nicht klug gewählt, da ich ja nur 0 drauf rechne.

Nun muss ich das ganze Prozedere für den neuen Wert 2,2 wieder 
machen...; und es geht von vorne los.

Gibts da nicht was einfacheres? Kann man nicht im Vorfeld schon 
irgendwie erkennen welche Werte gleich bleiben werden? Naja, die 
Diagonal-Werte sind ja klar...

[Arc N. (arc)]

Floyd-Warshall liegt in O(|V|^3), was spricht dagegen z.B. den 
Johnson-Algorithmus zu verwenden?

[Hans W. (Gast)]

Gegen diesen Johnson-Algorithmus spricht, dass die Aufgabe von mir 
explizit verlangt, dass der Floyd-Warshall-Algorithmus zum Einsatz 
kommt...

Hast du mein Vorgehen vielleicht kurz überprüft? Mach ich das richtig 
bei diesem Floyd-Warshall?

[Yalu X. (yalu) (Moderator)]

Hans Wurst schrieb:
> Mach ich das richtig bei diesem Floyd-Warshall?

So ganz habe ich nicht verstanden, wann du welche Vergleiche wie oft
durchführst. Schreibe den Algorithmus doch mal in Pseudo-Code (mit
Schleifen und if-Abfragen) auf und poste ihn hier oder vergleiche ihn
mit dem hier

  http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall

Wie Arc Net schrieb, braucht der Algorithmus n³ Schleifendurchläufe,
wenn n die Anzahl der Knoten ist.

Wichtig dabei ist, dass die äußere Schleife über die "Zwischenstatio-
nen" (bei dir a, im Wikipedia k) läuft und die innere über die
jeweils zu modifizierenden Matrixfelder. Würde man die äußere und die
innere Schleife vertauschen, käme ein falsches Ergebnis heraus, oder man
müsste das Verfahren solange wiederholen, bis sich die Matrixelemente
nicht mehr ändern. Dann wird der Aufwand natürlich größer als n³. Viel-
leicht rühren deine Zweifel von daher.

[Läubi .. (laeubi)]

Hans Wurst schrieb:
> Wenn ich das so  mache, wie ich das gelernt hab,
> braucht man da ja ewig für!
Siehst du, und deshalb hat man den Computer erfunden, nein nicht um 
damit Angry birds zu spielen ;-)

Und falls es so wie es sich anhört eine Hausaufgabe ist, wird der 
Aufgabensteller das Problem hoffentlich so klein gewählt haben, das du 
innerhalb der Bearbeitungszeit das Problem auch per Hand terminieren 
solltest :-)

[Hans W. (Gast)]

Ja, du hast natürlich Recht. Ich bastel da nun schon einige Zeit rum. 
Ich hab euch nochmal ein Bild hochgeladen, dass nun die D^1 Matrix 
zeigt. Ich wäre euch sehr zu Dank verpflichtet wenn sich jemand die Mühe 
machen würde und von D^0 auf D^1 kontrollieren würde!

Das wär echt super Nett von euch!

[Arc N. (arc)]

Hans Wurst schrieb:
> Ja, du hast natürlich Recht. Ich bastel da nun schon einige Zeit rum.
> Ich hab euch nochmal ein Bild hochgeladen, dass nun die D^1 Matrix
> zeigt. Ich wäre euch sehr zu Dank verpflichtet wenn sich jemand die Mühe
> machen würde und von D^0 auf D^1 kontrollieren würde!

Welche Mühe? Das ist nur ein Fünfzeiler + die Initialisierung der 
Distanzmatrix.

D^1 sieht so weit richtig aus...

[Hans W. (Gast)]

Hey, Danke für deine Hilfe!

Ich hab hier jetzt mal alle 6 Distanzmatrizen von Hand berechnet. Ich 
würd nun gerne wissen ob da noch irgendwo ein Fehler drin steckt. Das 
heißt, entweder du überprüfst mein Ergebnis oder du versuchst mir 
irgendwie aus deinem Programm die Lösung zukommen zulassen?

Ich würd mich jedenfalls riesig über die Hilfe freuen!

[Läubi .. (laeubi)]

Was gefällt dir an den in Wiki verlinkten Demonstratoren nicht?
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization
Bei dem einen kannst du sogar deinen Graphen malen und es dir 
visualisieren lassen...

[Arc N. (arc)]

Passt!

    let inf = infinity
    let mutable dist = array2D [ [ 0.0; inf; inf; inf; -1.0; inf];
                                 [ 1.0; 0.0; inf; 2.0; inf; inf ];
                                 [ inf; 2.0; 0.0; inf; inf; -8.0];
                                 [ -4.0; inf; inf; 0.0; 3.0; inf];
                                 [ inf; 7.0; inf; inf; 0.0; inf];
                                 [ inf; 5.0; 10.0; inf; inf; 0.0];
                               ]
    
    let floydWarshall numNodes (dist : float [,]) =
        for k in 0 .. numNodes - 1 do
            for i in 0 .. numNodes - 1 do
                for j in 0 .. numNodes - 1 do
                    if dist.[i, k] + dist.[k, j] < dist.[i, j] then 
                        dist.[i, j] <- dist.[i, k] + dist.[k, j]
            // printfn "%A\n" dist

// infinity durch inf ersetzt
[[0.0; inf; inf; inf; -1.0; inf]
 [1.0; 0.0; inf; 2.0; 0.0; inf]
 [inf; 2.0; 0.0; inf; inf; -8.0]
 [-4.0; inf; inf; 0.0; -5.0; inf]
 [inf; 7.0; inf; inf; 0.0; inf]
 [inf; 5.0; 10.0; inf; inf; 0.0]]

[[0.0; inf; inf; inf; -1.0; inf]
 [1.0; 0.0; inf; 2.0; 0.0; inf]
 [3.0; 2.0; 0.0; 4.0; 2.0; -8.0]
 [-4.0; inf; inf; 0.0; -5.0; inf]
 [8.0; 7.0; inf; 9.0; 0.0; inf]
 [6.0; 5.0; 10.0; 7.0; 5.0; 0.0]]

[[0.0; inf; inf; inf; -1.0; inf]
 [1.0; 0.0; inf; 2.0; 0.0; inf]
 [3.0; 2.0; 0.0; 4.0; 2.0; -8.0]
 [-4.0; inf; inf; 0.0; -5.0; inf]
 [8.0; 7.0; inf; 9.0; 0.0; inf]
 [6.0; 5.0; 10.0; 7.0; 5.0; 0.0]]

[[0.0; inf; inf; inf; -1.0; inf]
 [-2.0; 0.0; inf; 2.0; -3.0; inf]
 [0.0; 2.0; 0.0; 4.0; -1.0; -8.0]
 [-4.0; inf; inf; 0.0; -5.0; inf]
 [5.0; 7.0; inf; 9.0; 0.0; inf]
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]

[[0.0; 6.0; inf; 8.0; -1.0; inf]
 [-2.0; 0.0; inf; 2.0; -3.0; inf]
 [0.0; 2.0; 0.0; 4.0; -1.0; -8.0]
 [-4.0; 2.0; inf; 0.0; -5.0; inf]
 [5.0; 7.0; inf; 9.0; 0.0; inf]
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]

[[0.0; 6.0; inf; 8.0; -1.0; inf]
 [-2.0; 0.0; inf; 2.0; -3.0; inf]
 [-5.0; -3.0; 0.0; -1.0; -6.0; -8.0]
 [-4.0; 2.0; inf; 0.0; -5.0; inf]
 [5.0; 7.0; inf; 9.0; 0.0; inf]
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]

[Hans W. (Gast)]

Läubi .. schrieb:
> Was gefällt dir an den in Wiki verlinkten Demonstratoren nicht?
> 
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization
> 
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization
> Bei dem einen kannst du sogar deinen Graphen malen und es dir
> visualisieren lassen...

Oh, ich hab zwar den Artikel gelesen, aber nicht gesehen, dass da sogar 
so ein Applet verlinkt ist, dass mir weiterhilft! Aber jetzt weiß ich es 
ja!


Auch ein ganz großes Dankeschön an Arc Net! Vielen Dank!



Ihr alle habt mir sehr geholfen! Danke!