Floyd Algorithmus: Unterschied zwischen den Versionen

Version vom 30. Januar 2008, 13:35 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

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

Wintersemester 2007/2008

Vorlesungsmitschnitt zum Thema Floyd-Algorithmus aus dem Wintersemester 2007/2008

Wintersemester 2006/2007

• 31.10.2006
  • Floyd 31.10.2006 (Download)
  • Floyd 31.10.2006 (Stream)
  • Floyd 31.10.2006 (scaled Stream)
• 07.11.2006
  • Floyd 07.11.2006 (Download)
  • Floyd 07.11.2006 (Stream)
  • Floyd 07.11.2006 (scaled Stream)

Achtung: die Dateien aus dem WS 06/07 können fehlerhaft sein!
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.