6.4.1 Algorithmus von Floyd

Der hier beschriebene Algorithmus ist der Algorithmus von Floyd. Zwei Anwendungen dieses Algorithmus bzw. der Variante von Dijkstra sollen nun vorgestellt werden:

1.

Bottleneck: Der Bottleneck eines Weges ist die Kante des Weges mit den billigsten Kosten. Dies ist z.B. dann sinnvoll, wenn die Kosten die Kapazitäten oder Tragfähigkeiten modellieren. Gesucht ist dann also ein Weg von A nach B , dessen billigste Kante möglichst teuer (groß) ist. Diesen Weg findet man durch Anwendung des Floyd- bzw. Dijkstra-Algorithmus, nur daß man statt die Kantenkosten aufzuaddieren sie minimiert und statt den billigsten den teuersten Weg vorzieht.

2.

Zuverlässigkeitsproblem: In einem Kommunikationsnetzwerk sei p(i,j) die Erfolgswahrscheinlichkeit für die Verbindung von i nach j für alle (i,j) $\in$ E . Die Sicherheit einer Verbindung ist dann gleich dem Produkt der Erfolgswahrscheinlichkeiten p(i,j) der beteiligten Kanten. Gesucht ist dann also der sicherste Weg von A nach B . Dazu modifiziert man die Kantenkosten p(i,j) in - log (p(i,j)) . Der kürzeste Weg von A nach B in diesem modifizierten Graphen ist dann die sicherste Verbindung.

Bei kürzesten Wege Problemen haben wir bisher immer positive Kantenkosten vorausgesetzt und so die Existenz von negativen Zyklen ausgeschlossen. Im folgenden soll nun ein Algorithmus zur Berechnung der kürzesten Wege vorgestellt werden, der auch bei negativen Kantenkosten - im Gegensatz zu den bisherigen Algorithmen - korrekt arbeitet: Der Algorithmus von Floyd ist eine Alternative zu Dijkstra bei single source shortest path.

Gegeben: G = (V,E) mit zum Teil negativen Kosten

Gesucht: kürzester Weg von Knoten A zum Knoten B

Ähnlich wie bei Dijkstra ersetzt man m[y] durch m[x] + c(x,y) solange es eine Kante (x,y) mit m[x] + c(xy) < m[y] gibt.

Im i -ten Durchgang bestimmt man

Falls nach dem (n - 1) -ten Durchgang immer noch eine Verbesserung der m ⁱ[y] -Werte entsteht, so liegt ein negativer Zyklus in G vor, das Problem ist also unbeschränkt.

Auch im all shortest path Algorithmus nach Floyd, welcher negative Kantenkosten verkraftet, muß man überprüfen, ob ein negativer Zyklus vorliegt. Dies ist genau dann der Fall, wenn in der Hauptdiagonalen aller d ^k-Matrizen ein negativer Eintrag zu finden ist. Das Problem ist in diesem Fall nicht mehr sinnvoll.