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.
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.
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