Algoritme van Bellman-Ford

Het algoritme van Bellman-Ford is een graaf-algoritme dat, voor een gegeven knoop van een gerichte graaf, de kortste route naar alle knopen van die graaf bepaalt. 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

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), en
• 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 toekent, en
• ${\mathit {voorganger}}\colon V\to V$ een 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 $\scriptstyle v\in V$               
 02      $\scriptstyle {\mathit {afstand}}(v):=\infty$, $\scriptstyle {\mathit {voorganger}}(v):={\text{geen}}$
 03  $\scriptstyle {\mathit {afstand}}(s):=0$
 
 04  herhaal $\scriptstyle n-1$ keer              
 05      voor elke $\scriptstyle (u,v)\in E$
 06          als $\scriptstyle {\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)\ <\ {\mathit {afstand}}(v)$ dan
 07              $\scriptstyle {\mathit {afstand}}(v):={\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)$
 08              $\scriptstyle {\mathit {voorganger}}(v):=u$
   
 09  voor elke $\scriptstyle (u,v)\in E$        
 10      als $\scriptstyle {\mathit {afstand}}(u)+{\mathit {gewicht}}(u,v)\ <\ {\mathit {afstand}}(v)$ dan
 11      STOP met uitkomst "Er is een negatieve cirkel"
 
 13  uitkomst $\scriptstyle {\mathit {afstand}}$ en $\scriptstyle {\mathit {voorganger}}$

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

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