Vereinbarungen

Der Algorithmus von Bellmann und Ford kann auch auf Graphen mit negativen Kantengewichten angewandt werden, er kann daher durchaus als Verallgemeinerung des Algorithmus von Dijkstra verstanden werden.

Im Folgenden wird mit Hilfe des Graphen in Abbildung 14 gezeigt, wie der Algorithmus funktioniert. Das Beispiel ist an die Beschreibungen in [7] angelehnt. Der Algorithmus stammt aus [3] und [1] und wurde von Ford (1956) und Bellmann (1958) vorgeschlagen.

Auch hier wird ein Teilgraph über den Ausgangsgraphen wachsen gelassen. Im Unterschied zu Dijkstra - und das ist ganz wesentlich - werden Knoten allerdings zu keinem Zeitpunkt abschließend betrachtet. Die kürzeste Entfernung eines Knotens zum Ausgangsknoten steht also erst dann fest, wenn der Algorithmus endet. Gleichwohl gibt es immer wieder bisher kürzeste Entfernungen der Knoten.

Auch hier wird eine Kategorisierung der Knoten und Kanten vorgenommen. Für die Knoten wird festgelegt:

• Grüne Knoten sind vorläufig abschließend betrachtet. Es kann also ein Ereignis eintreten, welches die Knoten wieder rot färbt. Danach müssen die umgefärbten Knoten erneut besucht werden.

• Rote Knoten sind Knoten für die entweder erstmalig die Entfernung festgelegt wurde oder für die die Entfernung korrigiert wurde, die also bereits grün waren.

• Weiße Knoten sind noch nicht im wachsenden Teilgraphen enthalten, mithin also Knoten des Ausgangsgraphen.

Für Kanten wird festgelegt:

• Grüne Kanten sind Kanten, die auf einem vorläufig kürzesten Weg vorkommen.

• Rote Kanten sind Kanten des Teilgraphen, die vorläufig nicht auf einem kürzesten Weg vorkommen.

• Weiße Kanten sind alle Kanten aus dem Ausgangsgraphen, die noch nicht im Teilgraphen enthalten sind.