Floyd Algorithmus

Grundlegendes Konzept

In der Graphentheorie unterscheidet man zwei grundsätzliche Fragestellungen bei der Berechnung kürzester Wege: Im ersten Fall möchte man den kürzesten Weg zwischen einem definierten Startknoten und einem definierten Endknoten bestimmen. Diese Aufgabe wird mit dem Dijkstra Algorithmus gelöst. Der zweite Fall sucht die kürzesten Wege von allen Knoten zu allen anderen Knoten, d.h. zwischen jedem Knoten als Anfangsknoten und jedem Knoten als Endknoten (vgl. HMM 7.3). Dieses könnte man mit einer Aufstellung aller möglichen Bäume und der Berechnung mit Hilfe des Dijkstra-Algorithmus lösen. Allerdings wäre dies sehr aufwendig. Einfacher kann ein solches Problem mit Hilfe des Floyd-Algorithmus gelöst werden. Der nach Robert Floyd benannte Algorithmus ist sehr einfach zu berechnen, und lässt sich ebenso leicht programmieren. Die Grundidee besteht darin, dass man die Länge des Weges eines Knotens i zu einem Knoten j mit dem Umweg über den Knoten 1 vergleicht. Ist der „Umweg“ über Knoten 1 kürzer als der direkte Weg, so wird der alte verworfen. Sobald alle Wege über den Umwegknoten 1 verglichen sind, vergleicht man alle Wege über den Umwegknoten 2, usw…

Formelschreibweise

Man kann das Verfahren vereinfacht durch folgenden Pseudocode beschreiben:

   Für k=1 to n 
     Für i=1 to n (ex k)
       Für j=1 to n (ex k,i)
            Falls dij > dik + dkj dann
	     dij = dik + dkj  und            
            vij = vkj (falsch vij = k)

Dabei ist d_ij der Abstand des Knotens i vom Knoten j. Die Variable k stellt den Umwegknoten und v den Vorgängerknoten dar.

Erläuterung am Beispiel

Zur Veranschaulichung der Vorgehensweise wollen wir folgendes Beispiel betrachten. Die Entfernungen, sowie die Vorgängerknoten, sind dabei in der Matrix eingetragen. Im ersten Schritt wollen wir nun die Entfernungen aller Knoten (außer dem Knoten 1) untereinander mit dem Umweg über den Knoten 1 vergleichen. Zur besseren Übersichtlichkeit sind die Entfernung zum / vom Knoten 1 gelb hinterlegt. Nun vergleicht man z.b. den Weg von Knoten 2 zu Knoten 3 mit dem Umweg über Knoten 1. Der direkte Weg d₂₃ beträgt 1 LE, der Umweg d₂₁ + d₁₃ = 3 + 5 = 8 LE. Somit bleibt die alte Verbindung bestehen, da sie die kürzeste ist. Nach diesem Schema werden nun alle möglichen Verbindungen Weg für Weg kontrolliert ( Die Verbindungen 11, 22, 33 usw. sind natürlich ohne Bedeutung, und daher mit 0 angegeben). Dabei stellt man in diesem Beispiel fest, dass der Umweg über den Knoten 1 nie zu einer Verbesserung führt.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 1: Umwegknoten k=1

Somit kommen wir zum zweiten Schritt, in dem die Umwege über den Knoten 2 gebildet werden. Man beginnt mit dem Vergleich des Weges 13 mit dem Umweg 12 +23 und stellt dabei fest, dass der ursprüngliche Weg mit 5 LE länger ist, als der Umweg mit 3 + 1 = 4 LE. Man vermerkt daher in der Matrix die neue Länge mit dem neuen Vorgängerknoten 2. Ein direkter Weg zwischen Knoten 1 und Knoten 4 (und auch 5) besteht nicht und ist daher mit der Länge unendlich vermerkt. Der Umweg über den Knoten 2 bringt allerdings einen endlichen Wert, nämlich 7 (8), und ersetzt daher den Alten. Es werden wiederum alle restlichen Wege verglichen und, falls eine Verbesserung möglich ist, ersetzt. Die weiteren Veränderungen durch die Wahl des Umwegknotens 2 finden sie in Tabelle 2.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 2: Umwegknoten k=2

Getreu dem Schema wird nun mit den Vergleichen über die Umwegknoten 3 und 4 fortgefahren, bis die optimale Lösung gefunden ist. Ein wichtiges Beispiel möchte ich dabei noch herausstellen: Der Weg von Knoten 4 zu Knoten 1 über den Umwegknoten 3. Es ist abzulesen, dass der direkte Weg 41 bisher 10 LE beträgt (mit Umweg über 2). Betrachtet man den Umweg über den Knoten 3, erhält man 2 + 4 = 6 LE. Hierbei ist aber jetzt ein wichtiger Punkt zu beachten. Beim Weg von Knoten 3 zu Knoten 1, wird ein Umweg über 2 genommen, womit sich der komplette Weg nun zu 4-3-2-1 ergibt. Somit ist der direkte Vorgänger des Knotens 1 der Knoten 2 (und nicht der Umwegknoten 3). Dieser Fall tritt auch noch z.B. beim Weg 51 auf.
Die weiteren Schritte, sowie die optimale Lösung sind in den Tabellen 3, 4 und 5 dargestellt.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 3: Umwegknoten k=3

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 4: Umwegknoten k=4

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 5: bereinigte Optimallösung

Zusammenfassung

Zum Abschluss wollen wir die Schritte des Floyd-Algorithmus noch einmal kurz und knapp darstellen:

1. Vergleich des Weges von Knoten i zu Knoten j mit dem Umweg von i nach j über den Knoten 1. Ist der Umweg kürzer als der alte Weg, wird dieser durch den Umweg ersetzt (für alle i, j).
2. Wie Schritt 1, nur werden die Umwege über den Knoten 2 gebildet
3. Wie Schritt 1, nur werden die Umwege über den Knoten 3 gebildet
4. .... -> Wie Schritt 1, nur werden die Umwege über den Knoten k gebildet

Flash Animation

Wenn Sie sich eingehender mit dem Dijkstra-Algorithmus auseinandersetzen wollen, könnn Sie anhand einer Flash Animation weitere Beispiele bearbeiten.

Vorlesung/Lecture

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Floyd-Algorithmus (English)

Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.

Fundamental Concept

Graph theory distinguishes between two different fundamental questions in the calculation of shortest paths. The first case wants to calculate the shortest path between a previously defined start and end node. For this case Dijkstra-Algorithm delivers a solution. The second case searches all shortest paths from all nodes to all other nodes. That means every node may be an initial node from which we begin to calculate all shortest path to other nodes (cf. HMM 7.3). This problem may be solved by listing all possible trees and thereafter application of Dijkstra-Algorithm. However, this approach would be very intricate. A much more easier way to solve this problem offers Floyd-Algorithm. Floyd-Algorithm,named after Robert Floyd, is easily calculable and also programmable.The main idea is to compare the direct path between node i and j with the path containing a detour via node 1. If 'detour' via node 1 is shorter than the direct path, the old one will be discarded. Once all distances via detour node 1 are compared, one continues comparing all distances via detour node 2, and so on.

Formula notation

The prodedure may be described simplified by following pseudocode:

   For k=1 to n 
     For i=1 to n (ex k)
       For j=1 to n (ex k,i)
            If dij > dik + dkj then
	     dij = dik + dkj  and            
            vij = vkj (falsch vij = k)

d_ij characterizes the distance between node i and node j. Variable k identifies the detour node, while variable v the predecessor node.

Exemplification

The following example will be considered to illustrate the procedure. Distances as well as predecessor nodes are registered in the matrix. Firstly we compare the distances of all nodes expect node 1 among themselves with a detour via node 1. To improve the clarity distances from/to node 1 are marked yellow . Now single distances will be compared with the same path including the detour via node for example we consider path 2 to 3: The direct way d₂₃ from node 2 to node 3 amounts to 1 LU while the path including a detour via node 1 counts d₂₁ + d₁₃ = 3 + 5 = 8 LU. Thus the old connection which provides the shortest one persists. According to this schema each possible connection will be controlled (Since connections like 11,22,33 are irrelevant they are denoted as 0). In this case no detour via node 1 provides a contraction of the distance.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 1: Umwegknoten k=1

Now paths with a detour via node 2 will be considered and compared. We start with the comparison of path 13 with a detour 12 + 23 and register that the original path with 5LU is longer than the new detected connection with 3 + 1= 4 LU. So the new distance of 4LU and predecessor node 2 are noted in the matrix. A direct connection of node 1 and 4 is not possible and hence noted as a distance of infinite LU. A detour via node 2 (path: 12 + 24 =14)delivers a finite value namely 10 LU (12:3LU, 24: 7LU--> 14:10LU). All possible connections have to be compared and in case of improvement registered in the matrix.Further changes caused by a detour via node 2 can be seen in table 2.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 2: Umwegknoten k=2

According to the previously explained procedure paths including detours via node 3 and 4 will be compared, until an optimal solution is found. In this context an important example is to be explained: The path from node 4 to node 1 via node 3. As it can be seen in the table the distance was up to now 10 LU( detour via node 2). Considering a detour via node 3 the distance shortens to 2+4=6 LU (43 + 31 = 41). In this point the attention has to be paid to the predecessor node. The path 31 from node 3 to node 1 includes a detour via node 2 (3-2-1). Consequently the total path from node 4 to node 1 is passed in the following order of nodes :4-3-2-1. As it can be seen the direct predecessor of node 1 is node 2 ( and not detour node 3). The same problem also arises for example in path 51. Further steps as well as the optimal solution are illustrated in tables 3, 4 and 5.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 3: Umwegknoten k=3

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 4: Umwegknoten k=4

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle 5: bereinigte Optimallösung

Summary

Finally we want to sum up briefly a step-by-step procedure of Floyd-Algorithm:

1. Comparison of paths from node i to node j with a detour via node 1. If the newer one is shorter than the old one, the old one will be replaced (for all i,j)
2. Same procedure as step 1, except node 2 is the detour node instead of node 1
3. Same procedure as step 1, except node 3 as detour node
4. ...-> Procedure in step 1, except detour node is node k--> last iteration

Lecture

A video lecture on this topic is available.

Floyd-Algorithmus (English)

Please consider the following points to watch this lecture: Hinweise zum Betrachten