Floyd Warshall - Versionsgeschichte

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:04:34Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Thoronador: Kategorisierung hinzugefügt.

2008-05-01T16:13:32Z

Kategorisierung hinzugefügt.

Thoronador am 20. April 2008 um 14:31 Uhr

2008-04-20T14:31:18Z

Lyr: /* Kritik */ O-Notation-Links

2006-06-30T15:42:37Z

‎Kritik: O-Notation-Links

Flash: Neuer Artikel

2006-06-30T10:50:50Z

Neuer Artikel

Neue Seite

==Eigenschaften==
Der Floy Warshall Algorithmus findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.

Der Graph darf negative Kanten enthalten aber Vorraussetzung ist, dass '''keine negativen Kreise''' im Graph enthalten sind. (Kreise die negative Kosten verursachen.)

==Algorithmus==
Der Algorithmus basiert auf einer (Adjazenz-)Matrix. Die Knoten des Graphen werden als Index verwendet.
Der Zeilenindex stellt den Startknoten dar, der Spaltenindex den Zielknoten.

<pascal>
T[1..n][1..n] of integer; //n = Anzahl der Knoten

//Initialisierung
Matrix mit Maximalwert initialisieren.
Hauptdiagonale mit 0 initialisieren

for i := 1 to n do
for each Nachbar j von i do
T[i][j] = Kosten(i nach j);

//Eigentliches bestimmen der kürzesten Wege
for z := 1 to n do //z = zwischenknoten
for i := 1 to n do //i = startknoten
for j := 1 to n do //j = Zielknoten
if (T[i][z] + T[z][j]) < T[i][j]) then //"Wenn der Weg über den Zwischenknoten z besser ist
T[i][j] := T[i][z] + T[z][j]; // als der direkte, nimm diesen Weg."
</pascal>

Falls auf der Hauptdiagonale irgendwann ein Wert kleiner 0 steht hat man einen negativen Kreis gefunden. Dadurch ist nicht mehr sichergestellt, dass die Ergebnisse korrekt sind.

Am Ende des Algorithmus stehen in T[i][j] die minimalen Kosten um von i nach j zu kommen.
Steht in T[i][j] der Maximalwert (siehe Initialisierung) ist j von i aus nicht erreichbar.

==Kritik==
'''Vorteile:'''
*Der Algorithmus findet die minimalen Kosten von '''allen''' Wegen im Graph.
*Der Algorithmus ist deshalb besonders geeignet um die kürzesten Wege in statischen Netzwerken zu finden, da er nur einmal ausgeführt werden muss.

'''Nachteile:'''
*Der Algorithmus muss bei Änderungen des Netzwerks erneut aufgerufgen werden und berechnet dann alles neu.
*Der Algorithmus benötigt O(n²) Speicherplatz.
*Mit einer '''Laufzeit von O(n³)''' ist er nicht besonders schnell.

@@ Zeile 1: / Zeile 1: @@
 ==Eigenschaften==
-Der Floyd-Warshall-Algorithmus findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.
+Der '''Floyd-Warshall-Algorithmus''' (benannt nach Robert Floyd und Stephen Warshall) findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.
 Der Graph darf negative Kanten enthalten, aber Vorraussetzung ist, dass '''keine negativen Kreise''' im Graph enthalten sind (d.h. Kreise die negative Kosten verursachen).
@@ Zeile 43: / Zeile 44: @@
 *Der Algorithmus benötigt [[O-Notation|O]](n²) Speicherplatz.
 *Mit einer '''Laufzeit von [[O-Notation|O]](n³)''' ist er nicht besonders schnell.

@@ Zeile 10: / Zeile 10: @@
 Der Zeilenindex stellt den Startknoten dar, der Spaltenindex den Zielknoten.
-<pascal>
+<source lang="pascal">
 T[1..n][1..n] of integer; //n = Anzahl der Knoten
@@ Zeile 27: / Zeile 27: @@
        if (T[i][z] + T[z][j]) < T[i][j]) then //"Wenn der Weg über den Zwischenknoten z besser ist
            T[i][j] := T[i][z] + T[z][j];      // als der direkte, nimm diesen Weg."
-</pascal>
+</source>
 Falls auf der Hauptdiagonale irgendwann ein Wert kleiner 0 steht, dann hat man einen negativen Kreis gefunden. Dadurch ist nicht mehr sichergestellt, dass die Ergebnisse korrekt sind.

@@ Zeile 1: / Zeile 1: @@
 ==Eigenschaften==
-Der Floy Warshall Algorithmus findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.
+Der Floyd-Warshall-Algorithmus findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.
-Der Graph darf negative Kanten enthalten aber Vorraussetzung ist, dass '''keine negativen Kreise''' im Graph enthalten sind. (Kreise die negative Kosten verursachen.)
+Der Graph darf negative Kanten enthalten, aber Vorraussetzung ist, dass '''keine negativen Kreise''' im Graph enthalten sind (d.h. Kreise die negative Kosten verursachen).
@@ Zeile 20: / Zeile 20: @@
       T[i][j] = Kosten(i nach j);
-//Eigentliches bestimmen der kürzesten Wege
+//Eigentliches Bestimmen der kürzesten Wege
-for z := 1 to n do        //z = zwischenknoten
+for z := 1 to n do        //z = Zwischenknoten
-   for i := 1 to n do      //i = startknoten
+   for i := 1 to n do      //i = Startknoten
      for j := 1 to n do    //j = Zielknoten
        if (T[i][z] + T[z][j]) < T[i][j]) then //"Wenn der Weg über den Zwischenknoten z besser ist
@@ Zeile 28: / Zeile 28: @@
 </pascal>
-Falls auf der Hauptdiagonale irgendwann ein Wert kleiner 0 steht hat man einen negativen Kreis gefunden. Dadurch ist nicht mehr sichergestellt, dass die Ergebnisse korrekt sind.
+Falls auf der Hauptdiagonale irgendwann ein Wert kleiner 0 steht, dann hat man einen negativen Kreis gefunden. Dadurch ist nicht mehr sichergestellt, dass die Ergebnisse korrekt sind.
-Am Ende des Algorithmus stehen in T[i][j] die minimalen Kosten um von i nach j zu kommen.
+Am Ende des Algorithmus stehen in T[i][j] die minimalen Kosten, um von i nach j zu kommen.
-Steht in T[i][j] der Maximalwert (siehe Initialisierung) ist j von i aus nicht erreichbar.
+Steht in T[i][j] der Maximalwert (siehe Initialisierung), ist j von i aus nicht erreichbar.
@@ Zeile 37: / Zeile 37: @@
 '''Vorteile:'''
 *Der Algorithmus findet die minimalen Kosten von '''allen''' Wegen im Graph.
-*Der Algorithmus ist deshalb besonders geeignet um die kürzesten Wege in statischen Netzwerken zu finden, da er nur einmal ausgeführt werden muss.
+*Der Algorithmus ist deshalb besonders geeignet, um die kürzesten Wege in statischen Netzwerken zu finden, da er nur einmal ausgeführt werden muss.
 '''Nachteile:'''

@@ Zeile 41: / Zeile 41: @@
 '''Nachteile:'''
 *Der Algorithmus muss bei Änderungen des Netzwerks erneut aufgerufgen werden und berechnet dann alles neu.
-*Der Algorithmus benötigt O(n²) Speicherplatz.
+*Der Algorithmus benötigt [[O-Notation|O]](n²) Speicherplatz.
-*Mit einer '''Laufzeit von O(n³)''' ist er nicht besonders schnell.
+*Mit einer '''Laufzeit von [[O-Notation|O]](n³)''' ist er nicht besonders schnell.