Die Klasse Floyd löst das all-pairs-shortest-path-Problem
mit dem Algorithmus von Floyd. Für eine -Ausgangsmatrix C mit
den Kantenkosten werden sukzessive die (
)-Matrizen
berechnet. Die Matrix
enthält
die Kosten der kürzesten Wege zwischen zwei Knoten
und
,
die als Zwischenknoten nur die Knoten
verwenden. Setze
. Dann
lässt sich
errechnen durch das Minimum von
und
.
Um auch die zugehörige Kantenfolge rekonstruieren zu können,
wird parallel dazu eine Folge von -Matrizen
aufgebaut,
die an Position
den vorletzten Knoten auf dem kürzesten
Weg von
nach
notiert, der nur über die Zwischenknoten
läuft.
Source:
Floyd.java
JavaDoc:
Floyd.html
Source:
FloydTest.java
JavaDoc:
FloydTest.html
Applet: