Bellman-Ford Algorithm for Shortest Path

Der Algorithmus funktioniert durch iteratives Entspannen von Kanten: Für jede Kante wird geprüft, ob der Weg über diese Kante zu einem kürzeren Pfad zum Ziel führt als der aktuell beste bekannte Pfad. Durch Wiederholung dieses Prozesses für alle Kanten V-1 Mal, wobei V die Anzahl der Knoten ist, garantiert der Algorithmus das Finden des kürzesten Pfades auch bei negativen Gewichten. Die zentrale Erkenntnis ist, dass jeder kürzeste Pfad in einem Graphen mit V Knoten höchstens V-1 Kanten enthält; wenn sich die Distanzen nach V-1 Iterationen immer noch verbessern, muss ein negativer Zyklus existieren.