Brontekst bekijken van Algoritme van Bellman-Ford

Het '''algoritme van Bellman-Ford''' is een [[grafentheorie|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 <math>V</math> (van het Engelse ''vertices''),
* een verzameling zijden <math>E\subseteq V\times V</math> (van het Engelse ''edges''),
* een [[Afbeelding (wiskunde)|afbeelding]] <math>\mathit{gewicht} \colon E \to \Z</math> die aan elke zijde een gewicht toekent, en uit
* een startknoop <math>s \in V</math>.

Het algoritme bepaalt de kortste paden van <math>s</math> naar de andere knopen.
   
In het onderstaande algoritme is:
* <math>n</math> het aantal knopen in de verzameling <math>V</math>,
* <math>\mathit{afstand}\colon V\to\mathbb{Z}\cup\infty</math> een afbeelding die aan elke knoop een afstand vanaf de startknoop toekent, en
* <math>\mathit{voorganger}\colon V\to V</math> een partiële afbeelding die aan elke knoop een voorganger toekent. 
De afbeeldingen <math>\mathit{afstand}</math> en <math>\mathit{voorganger}</math> worden tijdens het uitvoeren van het algoritme opgebouwd.

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

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

In plaats van [[Geheel getal|gehele getallen]] (<math>\Z</math>) kunnen ook andere soorten getallen als gewichten worden gebruikt, bijvoorbeeld [[Rationaal getal|rationale getallen]] (<math>\Q</math>).

[[Categorie:Algoritme]]
[[Categorie:Grafentheorie]]