Algoritme van Bellman-Ford

Het algoritme van Bellman-Ford is een graaf-algoritme dat de kortste route bepaalt in een gerichte graaf. Het algoritme van Dijkstra lost dit probleem sneller op, maar dat algoritme kan alleen gebruikt worden bij een graaf met niet-negatieve gewichten. Het algoritme van Bellman-Ford wordt dus in de praktijk alleen gebruikt bij een graaf met negatieve gewichten. Het algoritme van Bellman-Ford kan namelijk een negatieve cirkel opsporen. Het algoritme is genoemd naar zijn ontwikkelaars, Richard Bellman en Lester Ford.

Het algoritme

• V is de verzameling van knopen (komt van het Engelse Vertex)
• E is de verzameling van bogen (komt van het Engelse Edge)

01  voor elke v uit V                   
02      afstand(v) := oneindig, voorganger(v) := geen
03  afstand(s) := 0

04  herhaal n - 1 keer               
05      voor elke (u,v) uit E
06          als afstand(u) + gewicht(u,v) < afstand(v)
07          dan
08              afstand(v) := afstand(u) + gewicht(u,v)
09              voorganger(v) := u

10  voor elke (u,v) uit E                
11      als afstand(u) + gewicht(u,v) < afstand(v) dan
12          STOP met uitkomst "Er is een negatieve cirkel"

13  uitkomst afstand