Floyd-Warshall-Algorithmus

Hans W. Gast #3023078
Lesenswert?
• ▲
▼ 
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...
Angehängte Dateien:
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Yalu X. Moderator #3023263
Lesenswert?
• ▲
▼ 
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.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Läubi .. Persönliche Seite #3023355
Lesenswert?
• ▲
▼ 
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 :-)
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Hans W. Gast #3023432
Lesenswert?
• ▲
▼ 
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!
Angehängte Dateien:
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Arc N. #3023585
Lesenswert?
• ▲
▼ 
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...
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Hans W. Gast #3024165
Lesenswert?
• ▲
▼ 
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!
Angehängte Dateien:
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Läubi .. Persönliche Seite #3024188
Lesenswert?
• ▲
▼ 
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...
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Arc N. #3024248
Lesenswert?
• ▲
▼ 
Passt!
1
    let inf = infinity

2
    let mutable dist = array2D [ [ 0.0; inf; inf; inf; -1.0; inf];

3
                                 [ 1.0; 0.0; inf; 2.0; inf; inf ];

4
                                 [ inf; 2.0; 0.0; inf; inf; -8.0];

5
                                 [ -4.0; inf; inf; 0.0; 3.0; inf];

6
                                 [ inf; 7.0; inf; inf; 0.0; inf];

7
                                 [ inf; 5.0; 10.0; inf; inf; 0.0];

8
                               ]

9
    

10
    let floydWarshall numNodes (dist : float [,]) =

11
        for k in 0 .. numNodes - 1 do

12
            for i in 0 .. numNodes - 1 do

13
                for j in 0 .. numNodes - 1 do

14
                    if dist.[i, k] + dist.[k, j] < dist.[i, j] then 

15
                        dist.[i, j] <- dist.[i, k] + dist.[k, j]

16
            // printfn "%A\n" dist



1
// infinity durch inf ersetzt

2
[[0.0; inf; inf; inf; -1.0; inf]

3
 [1.0; 0.0; inf; 2.0; 0.0; inf]

4
 [inf; 2.0; 0.0; inf; inf; -8.0]

5
 [-4.0; inf; inf; 0.0; -5.0; inf]

6
 [inf; 7.0; inf; inf; 0.0; inf]

7
 [inf; 5.0; 10.0; inf; inf; 0.0]]

8


9
[[0.0; inf; inf; inf; -1.0; inf]

10
 [1.0; 0.0; inf; 2.0; 0.0; inf]

11
 [3.0; 2.0; 0.0; 4.0; 2.0; -8.0]

12
 [-4.0; inf; inf; 0.0; -5.0; inf]

13
 [8.0; 7.0; inf; 9.0; 0.0; inf]

14
 [6.0; 5.0; 10.0; 7.0; 5.0; 0.0]]

15


16
[[0.0; inf; inf; inf; -1.0; inf]

17
 [1.0; 0.0; inf; 2.0; 0.0; inf]

18
 [3.0; 2.0; 0.0; 4.0; 2.0; -8.0]

19
 [-4.0; inf; inf; 0.0; -5.0; inf]

20
 [8.0; 7.0; inf; 9.0; 0.0; inf]

21
 [6.0; 5.0; 10.0; 7.0; 5.0; 0.0]]

22


23
[[0.0; inf; inf; inf; -1.0; inf]

24
 [-2.0; 0.0; inf; 2.0; -3.0; inf]

25
 [0.0; 2.0; 0.0; 4.0; -1.0; -8.0]

26
 [-4.0; inf; inf; 0.0; -5.0; inf]

27
 [5.0; 7.0; inf; 9.0; 0.0; inf]

28
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]

29


30
[[0.0; 6.0; inf; 8.0; -1.0; inf]

31
 [-2.0; 0.0; inf; 2.0; -3.0; inf]

32
 [0.0; 2.0; 0.0; 4.0; -1.0; -8.0]

33
 [-4.0; 2.0; inf; 0.0; -5.0; inf]

34
 [5.0; 7.0; inf; 9.0; 0.0; inf]

35
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]

36


37
[[0.0; 6.0; inf; 8.0; -1.0; inf]

38
 [-2.0; 0.0; inf; 2.0; -3.0; inf]

39
 [-5.0; -3.0; 0.0; -1.0; -6.0; -8.0]

40
 [-4.0; 2.0; inf; 0.0; -5.0; inf]

41
 [5.0; 7.0; inf; 9.0; 0.0; inf]

42
 [3.0; 5.0; 10.0; 7.0; 2.0; 0.0]]
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Hans W. Gast #3024276
Lesenswert?
• ▲
▼ 
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!
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren