Animation: Algorithmus von Floyd

Animation Systems Collection -- Animations Collection

Description

Der Algorithmus von Floyd berechnet für einen gegebenen gerichteten oder ungerichteten Graphen die kürzeste Verbindung aller Knoten zueinander. Im Gegensatz zum Algorithmus von Dijkstra wird also nicht nur die kürzeste Verbindung von einem Startknoten zu allen anderen Knoten betrachtet, sondern für jedes Paar v, w von Knoten der kürzeste Weg zwischen v und w berechnet.

Die grundlegende Idee dazu ist identisch zur Berechnung der transitiven Hülle und kann wie folgt skizziert werden:

Die kürzeste Verbindung der Knoten v, w zueinander ist

1. entweder die direkte Verbindung der Knoten, d.h. die Kante (v, w), falls diese existiert,
2. oder eine Verbindung zweier Wege von v nach k und von k nach w für einen bestimmten Knoten k.

Zur systematischen Berechnung der Kosten wird nun wie folgt verfahren:

1. Übernehme die direkten Kanten als (zunächst) billigste Verbindung der Knoten; falls keine direkte Kante existiert, setzte den Wert aus "unendlich" bzw. Integer.MAX_VALUE (die größte darstellbare ganze Zahl).
2. Wähle den nächsten Zwischenknoten x.
   Gibt es keinen weiteren Startknoten x, d.h. wurden schon alle Zwischenknoten getestet, ist die Rechnung abgeschlossen.
3. Wähle den nächsten Startknoten i. Gibt es keinen Weg i, x, fahre direkt mit diesem Schritt fort, indem der nächste Startknoten gewählt wird.

   Wurden schon alle Startknoten gewählt, fahre fort bei Schritt 2, d.h. wähle einen neuen Zwischenknoten.

4. Teste für jeden Zielknoten j, ob der Weg i, x zusammen mit dem Weg x, j billiger ist als der Weg i, j.
   Falls es keinen Weg x, j gibt, kann diese Rechnung schon früher abgebrochen werden.

   Ist der neue Weg billiger, trage seine Kosten in die Adjazenzmatrix an Position (i, j) ein.

5. Fahre fort bei Schritt 3, d.h. wähle den nächsten Startknoten bei gleichem Zwischenknoten.

Die Berechnung erfordert einen Aufwand von O(|V|³, da drei Schleifen über alle |V| Knoten auszuführen sind.

Verglichen mit der transitiven Hülle liegt der einzige Unterschied darin, daß für einen vorliegenden Weg getestet wird, ob er günstiger als der bereits bekannte ist (bzw. neu ist) und seine Kosten eingetragen werden. Die Berechnung der transitiven Hülle begügt sich damit, lediglich den Wert 1 in die Adjazenzmatrix einzutragen.

Screen Shot(s):

Algorithmus im Sourcecode mit Beispielgraph

Eintragung von neuen günstigeren Wegen

Classification

• Algorithms
• Graph Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Algorithmus von Floyd
Animation URL	http://www.animal.ahrgr.de/Anims/de/floyd.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	André Flöper
Date	1999-05-10
File Size size	6678 Byte
Number of Accesses:	9832
Added to DB by	Guido Rößling
Average Rating	4.6923(39 submitted ratings)
Language:	de
Number of Accesses:	9832

BibTeX bibliographic entry for citations:

@Misc{Flöper:1999,
   author = {André Flöper},
   title = {Algorithmus von Floyd},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/de/floyd.aml}},
 }