Algoritme van Bellman-Ford

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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

  • een verzameling knopen (van het Engelse vertices),
  • een verzameling zijden (van het Engelse edges), en
  • een afbeelding die aan elke zijde een gewicht toekent,

en uit een startknoop .

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

In het onderstaande algoritme is:

  • het aantal knopen in de verzameling ,
  • een afbeelding die aan elke knoop een afstand toekent, en
  • een afbeelding die aan elke knoop een voorganger toekent.

De afbeeldingen en worden tijdens het uitvoeren van het algoritme opgebouwd.

 01  voor elke                
 02      , 
 03  
 
 04  herhaal  keer              
 05      voor elke 
 06          als  dan
 07              
 08              
   
 09  voor elke         
 10      als  dan
 11      STOP met uitkomst "Er is een negatieve cirkel"
 
 13  uitkomst  en 

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

In plaats van gehele getallen () kunnen ook andere soorten getallen als gewichten worden gebruikt, bijvoorbeeld rationale getallen ().