Bellman–Ford-algoritmen
Vissa kortaste-väg-problem har kanter som gör en väg billigare: en återbetalning, en sträcka i nedförsbacke, en växelkurs till din fördel. Dem klarar inte Dijkstras algoritm. Det gör Bellman–Ford-algoritmen, genom att byta listighet mot tålamod.
Idén
Alla kortaste-väg-algoritmer bygger på ett enda drag, att relaxera en kant: om det är kortare att gå till u och sedan längs kanten u → v än den bästa kända vägen till v, använd den. Dijkstras algoritm relaxerar varje kant en gång, i en smart ordning som bara fungerar när ingen kant är negativ. Bellman–Ford antar inget sådant. Den relaxerar varje kant, i valfri fast ordning, om och om igen, tills avstånden slutar ändras.
Steg för steg
Ge starten avstånd 0 och alla andra noder oändligt. Upprepa n − 1 gånger för n noder: gå igenom varje kant u → v och relaxera den om u har ett avstånd. Sluta tidigt om ett helt varv inte ändrar något. Gör sedan ett varv till. Om någon kant fortfarande kan relaxeras kan en cykel med negativ summa nås från starten; annars är varje avstånd det kortaste, och de sparade noderna ger vägarna.
Ett exempel
Ta de enkelriktade kanterna A → B med längd 4, A → C 5, B → D 2 och C → B −3, kontrollerade i den ordningen, från A. Varv 1 ger B 4, C 5 och D 6, och sedan sänker C → B avståndet till B till 5 − 3 = 2. Varv 2 sänker D till 2 + 2 = 4. Varv 3 ändrar inget, så svaret är B 2, C 5, D 4. Dijkstras algoritm skulle ha gjort B slutgiltig på 4 och D på 6 innan den såg den negativa kanten. Lägg till en kant D → C med längd −4, så får cykeln C → B → D → C summan −5: varje varv sänker avstånden igen, och kontrollvarvet rapporterar det.
Varför n − 1 varv räcker
En kortaste väg, när en sådan finns, upprepar aldrig en nod, så den har högst n − 1 kanter. Att relaxera varje kant i ett varv förlänger varje korrekt känd kortaste väg med en kant till, oavsett kanternas ordning. Efter varv k stämmer alltså alla kortaste vägar med upp till k kanter, och efter n − 1 varv alla. Ordningen spelar ändå roll för hastigheten: med en bra ordning kan det vara klart efter ett eller två varv.
Historia och användning
Alfonso Shimbel beskrev metoden 1955, Lester Ford Jr. 1956, Edward F. Moore 1957 och Richard Bellman 1958; den bär namnen på två av dem, Bellman och Ford. Varven kan köras av varje router för sig, vilket gjorde den till grunden för distansvektorprotokoll för routning som RIP. Inom finans gör den negativa logaritmen av växelkurser en lönsam runda av valutaaffärer till en negativ cykel, som Bellman–Ford kan hitta.
Utforska den
Öppna appen och tryck på Steg. Varje kant är enkelriktad, och några längder är negativa. Varje steg kontrollerar en kant, i en fast ordning, och rutorna visar varvet och hur många avstånd det ändrade. Oftast ändrar ett varv snart inget och sökningen slutar tidigt. Kryssa i Lägg till en negativ cykel och se avstånden sjunka varv efter varv tills kontrollvarvet hittar cykeln och ritar den i rött.
Ofta ställda frågor
Vilken tidskomplexitet har Bellman–Ford?
O(V · E) för V noder och E kanter: upp till V − 1 varv som vart och ett kontrollerar varje kant. Med tidigt stopp är den ofta mycket snabbare i praktiken, och i bästa fall räcker ett enda varv.
Vad är en negativ cykel?
En cykel vars kantlängder tillsammans blir mindre än noll. Går man runt den om och om igen blir en väg hur kort som helst, så kortaste avstånd till varje nod som kan nås genom den är odefinierade.
Fungerar Bellman–Ford på oriktade grafer?
Bara om ingen kant är negativ: en oriktad negativ kant kan korsas fram och tillbaka, och det är en negativ cykel med två kanter. Med icke-negativa kanter fungerar den, men Dijkstras algoritm är snabbare.
Vad är SPFA?
Shortest Path Faster Algorithm, en version av Bellman–Ford som med en kö bara kontrollerar kanterna ut från noder vars avstånd just har ändrats på nytt. Den är ofta mycket snabbare, men dess värsta fall är detsamma.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova Bellman–Ford