Bellman–Ford-algoritmen

Nogle korteste-vej-problemer har kanter, der gør en vej billigere: en tilbagebetaling, et stykke ned ad bakke, en valutakurs i din favør. Dem kan Dijkstras algoritme ikke klare. Det kan Bellman–Ford-algoritmen, ved at bytte snilde for tålmodighed.

En graf med ensrettede pile, nogle kanter negative, afstandene indtil nu på knuderne og en negativ kreds tegnet med rødt
En graf med ensrettede pile, nogle kanter negative, afstandene indtil nu på knuderne og en negativ kreds tegnet med rødt

Idéen

Alle korteste-vej-algoritmer bygger på ét træk, at relaksere en kant: hvis det er kortere at gå til u og så ad kanten u → v end den bedste kendte vej til v, så brug den. Dijkstras algoritme relakserer hver kant én gang, i en smart rækkefølge, der kun virker, når ingen kant er negativ. Bellman–Ford antager ikke noget sådant. Den relakserer hver kant, i en vilkårlig fast rækkefølge, igen og igen, indtil afstandene holder op med at ændre sig.

Trin for trin

Giv starten afstand 0 og alle andre knuder uendelig. Gentag n − 1 gange for n knuder: gå hver kant u → v igennem, og relaksér den, hvis u har en afstand. Stop tidligt, hvis et helt gennemløb ikke ændrer noget. Lav så ét gennemløb mere. Kan en kant stadig relakseres, kan en kreds med negativ sum nås fra starten; ellers er hver afstand den korteste, og de huskede knuder giver vejene.

Et eksempel

Tag de ensrettede kanter A → B med længde 4, A → C 5, B → D 2 og C → B −3, undersøgt i den rækkefølge, fra A. Gennemløb 1 giver B 4, C 5 og D 6, og så sænker C → B B til 5 − 3 = 2. Gennemløb 2 sænker D til 2 + 2 = 4. Gennemløb 3 ændrer intet, så svaret er B 2, C 5, D 4. Dijkstras algoritme ville have gjort B endelig med 4 og D med 6, før den så den negative kant. Tilføj en kant D → C med længde −4, så giver kredsen C → B → D → C summen −5: hvert gennemløb sænker afstandene igen, og tjekgennemløbet melder det.

Hvorfor n − 1 gennemløb er nok

En korteste vej gentager aldrig en knude, når der findes en, så den har højst n − 1 kanter. At relaksere hver kant i et gennemløb forlænger hver korrekt kendt korteste vej med én kant mere, uanset kanternes rækkefølge. Så efter gennemløb k er alle korteste veje med op til k kanter rigtige, og efter n − 1 gennemløb dem alle. Rækkefølgen betyder stadig noget for hastigheden: med en god rækkefølge kan den blive færdig på et eller to gennemløb.

Historie og anvendelser

Alfonso Shimbel beskrev metoden i 1955, Lester Ford Jr. i 1956, Edward F. Moore i 1957 og Richard Bellman i 1958; den bærer navnene på to af dem, Bellman og Ford. Dens gennemløb kan køres af hver router for sig, hvilket gjorde den til grundlaget for distance vector-routingprotokoller som RIP. I finans gør den negative logaritme af valutakurser en profitabel runde af valutahandler til en negativ kreds, som Bellman–Ford kan finde.

Richard Bellman i 1962, fotograferet af Alfred Eisenstaedt. Han offentliggjorde metoden til korteste veje i 1958, efter Shimbel, Ford og Moore.
Richard Bellman i 1962, fotograferet af Alfred Eisenstaedt. Han offentliggjorde metoden til korteste veje i 1958, efter Shimbel, Ford og Moore.

Udforsk den

Åbn appen, og tryk på Trin. Hver kant er ensrettet, og nogle længder er negative. Hvert trin undersøger én kant, i en fast rækkefølge, og felterne viser gennemløbet, og hvor mange afstande det ændrede. Som regel ændrer et gennemløb snart intet, og søgningen stopper tidligt. Sæt kryds ved Tilføj en negativ kreds, og se afstandene falde gennemløb efter gennemløb, indtil tjekgennemløbet finder kredsen og tegner den med rødt.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten for Bellman–Ford?

O(V · E) for V knuder og E kanter: op til V − 1 gennemløb, som hver undersøger hver kant. Med tidligt stop er den ofte meget hurtigere i praksis, og i bedste fald er ét gennemløb nok.

Hvad er en negativ kreds?

En kreds, hvis kantlængder tilsammen giver mindre end nul. Går man rundt i den igen og igen, bliver en vej så kort, man vil, så korteste afstande til alle knuder, der kan nås gennem den, er udefinerede.

Virker Bellman–Ford på uorienterede grafer?

Kun hvis ingen kant er negativ: en uorienteret negativ kant kan krydses frem og tilbage, og det er en negativ kreds med to kanter. Med ikke-negative kanter virker den, men Dijkstras algoritme er hurtigere.

Hvad er SPFA?

Shortest Path Faster Algorithm, en udgave af Bellman–Ford, der med en kø kun undersøger kanterne ud fra knuder, hvis afstand lige er ændret, igen. Den er ofte meget hurtigere, men dens værste tilfælde er det samme.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv Bellman–Ford