Algoritme van Bellman-Ford

Het algoritme van Bellman-Ford is een graaf-algoritme dat, voor een gegeven knoop van een gerichte, gewogen graaf, de kortste route naar alle knopen van die graaf bepaalt. Het kortstepad-algoritme, ook bekend als het algoritme van Dijkstra, lost dit probleem sneller op, maar dat algoritme kan alleen bij een graaf met niet-negatieve gewichten worden gebruikt. 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 naar de ontwikkelaars ervan genoemd, Richard Bellman en Lester Ford.

Algoritme

De invoer van het algoritme bestaat uit een gewogen graaf, gegeven door

• een verzameling knopen $V$ (van het Engelse vertices),
• een verzameling zijden $E\subseteq V\times V$ (van het Engelse edges),
• een afbeelding ${\mathit {gewicht}}\colon E\to \mathbb {Z}$ die aan elke zijde een gewicht toekent, en uit
• een startknoop $s\in V$.

Het algoritme bepaalt de kortste paden van $s$ naar de andere knopen.

In het onderstaande algoritme is:

• $n$ het aantal knopen in de verzameling $V$,
• ${\mathit {afstand}}\colon V\to \mathbb {Z} \cup \infty$ een afbeelding die aan elke knoop een afstand vanaf de startknoop toekent, en
• ${\mathit {voorganger}}\colon V\to V$ een partiële afbeelding die aan elke knoop een voorganger toekent.

De afbeeldingen ${\mathit {afstand}}$ en ${\mathit {voorganger}}$ worden tijdens het uitvoeren van het algoritme opgebouwd.

 01  voor elke $v\in V$               
 02      ${\mathit {afstand}}(v):=\infty$, ${\mathit {voorganger}}(v):={\text{geen}}$
 03  ${\mathit {afstand}}(s):=0$
 
 04  herhaal $n-1$ keer              
 05      voor elke $(u,v)\in E$
 06          als ${\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)<{\mathit {afstand}}(v)$ dan
 07              ${\mathit {afstand}}(v):={\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)$
 08              ${\mathit {voorganger}}(v):=u$
   
 09  voor elke $(u,v)\in E$        
 10      als ${\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)<{\mathit {afstand}}(v)$ dan
 11      STOP met uitkomst "Er is een negatieve cirkel"
 
 12  uitkomst ${\mathit {afstand}}$ en ${\mathit {voorganger}}$

Als het algoritme klaar is en er geen cirkel met negatieve afstand is gevonden, levert ${\mathit {afstand}}$ voor iedere knoop kortste afstand van $s$ naar die knoop en kunnen met behulp van ${\mathit {voorganger}}$ de routes met het minste gewicht worden bepaald.

In plaats van gehele getallen ($\mathbb {Z}$) kunnen ook andere soorten getallen als gewichten worden gebruikt, bijvoorbeeld rationale getallen ($\mathbb {Q}$).