Het Bellman–Ford-algoritme

Bij sommige kortstepadproblemen zijn er kanten die een pad goedkoper maken: een terugbetaling, een stuk bergaf, een wisselkoers in je voordeel. Het algoritme van Dijkstra kan daar niet mee omgaan. Het Bellman–Ford-algoritme wel, door slimheid in te ruilen voor geduld.

Een graaf met eenrichtingspijlen, sommige kanten negatief, de afstanden tot nu toe op de knopen en een negatieve cyclus in rood
Een graaf met eenrichtingspijlen, sommige kanten negatief, de afstanden tot nu toe op de knopen en een negatieve cyclus in rood

Het idee

Elk kortstepadalgoritme draait om één zet, het relaxeren van een kant: als naar u gaan en dan langs de kant u → v korter is dan de beste bekende weg naar v, gebruik die dan. Het algoritme van Dijkstra relaxeert elke kant één keer, in een slimme volgorde die alleen werkt als geen kant negatief is. Bellman–Ford gaat daar niet van uit. Het relaxeert elke kant, in een willekeurige vaste volgorde, steeds opnieuw, tot de afstanden niet meer veranderen.

Stap voor stap

Geef de start afstand 0 en elke andere knoop oneindig. Herhaal n − 1 keer, voor n knopen: loop elke kant u → v langs en relaxeer hem als u een afstand heeft. Stop vroeg als een hele ronde niets verandert. Doe dan nog één ronde. Kan er nog een kant worden gerelaxeerd, dan is er vanaf de start een cyclus met een negatief totaal te bereiken; zo niet, dan is elke afstand de kortste, en geven de onthouden knopen de paden.

Een voorbeeld

Neem de eenrichtingskanten A → B met lengte 4, A → C 5, B → D 2 en C → B −3, in die volgorde bekeken, vanaf A. Ronde 1 geeft B 4, C 5 en D 6, en dan verlaagt C → B de afstand van B naar 5 − 3 = 2. Ronde 2 verlaagt D naar 2 + 2 = 4. Ronde 3 verandert niets, dus het antwoord is B 2, C 5, D 4. Het algoritme van Dijkstra zou B al op 4 en D op 6 definitief hebben gemaakt, voordat het de negatieve kant zag. Voeg een kant D → C met lengte −4 toe, en de cyclus C → B → D → C komt op −5: elke ronde verlaagt de afstanden opnieuw, en de controleronde meldt het.

Waarom n − 1 rondes genoeg zijn

Een kortste pad, als dat er is, komt nooit twee keer langs dezelfde knoop, dus het heeft hoogstens n − 1 kanten. Als je in een ronde elke kant relaxeert, wordt elk correct bekend kortste pad met nog één kant verlengd, in welke volgorde de kanten ook staan. Na ronde k kloppen dus alle kortste paden met hoogstens k kanten, en na n − 1 rondes allemaal. De volgorde maakt wel uit voor de snelheid: met een goede volgorde ben je in één of twee rondes klaar.

Geschiedenis en toepassingen

Alfonso Shimbel beschreef de methode in 1955, Lester Ford Jr. in 1956, Edward F. Moore in 1957 en Richard Bellman in 1958; ze draagt de namen van twee van hen, Bellman en Ford. Elke router kan de rondes zelfstandig uitvoeren, en daardoor werd ze de basis van distance-vector-routeringsprotocollen zoals RIP. In de financiële wereld maakt de negatieve logaritme van wisselkoersen van een winstgevende reeks valutatransacties een negatieve cyclus, die Bellman–Ford kan vinden.

Richard Bellman in 1962, gefotografeerd door Alfred Eisenstaedt. Hij publiceerde de methode voor kortste paden in 1958, na Shimbel, Ford en Moore.
Richard Bellman in 1962, gefotografeerd door Alfred Eisenstaedt. Hij publiceerde de methode voor kortste paden in 1958, na Shimbel, Ford en Moore.

Probeer het zelf

Open de app en druk op Stap. Elke kant is eenrichtingsverkeer, en sommige lengtes zijn negatief. Elke stap bekijkt één kant, in een vaste volgorde, en de tegels tonen de ronde en hoeveel afstanden die veranderde. Meestal verandert een ronde al snel niets meer en stopt het zoeken vroeg. Vink Negatieve cyclus toevoegen aan en zie de afstanden ronde na ronde dalen, tot de controleronde de cyclus vindt en rood tekent.

Veelgestelde vragen

Wat is de tijdcomplexiteit van Bellman–Ford?

O(V · E) voor V knopen en E kanten: hoogstens V − 1 rondes, die elk elke kant bekijken. Met vroeg stoppen is het in de praktijk vaak veel sneller, en in het beste geval is één ronde genoeg.

Wat is een negatieve cyclus?

Een cyclus waarvan de kantlengtes optellen tot minder dan nul. Wie er steeds weer omheen gaat, maakt een pad zo kort als hij wil, dus de kortste afstanden naar elke knoop die via de cyclus te bereiken is, bestaan niet.

Werkt Bellman–Ford op ongerichte grafen?

Alleen als geen kant negatief is: een ongerichte negatieve kant kun je heen en weer oversteken, en dat is een negatieve cyclus van twee kanten. Met niet-negatieve kanten werkt het, maar het algoritme van Dijkstra is sneller.

Wat is SPFA?

Het Shortest Path Faster Algorithm, een versie van Bellman–Ford die met een wachtrij alleen de kanten opnieuw bekijkt die vertrekken uit knopen waarvan de afstand net veranderd is. Het is vaak veel sneller, al is het slechtste geval hetzelfde.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer Bellman–Ford