Floyd Algorithmus: Unterschied zwischen den Versionen

Version vom 18. April 2014, 16:21 Uhr

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.

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.

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.

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.

Überarbeitete Englische Version (noch nicht korrigiert)

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.