- Aktuell
- Har ett avstånd
- Använd kant
- Väg
- Negativ cykel
Bellman–Ford-algoritmen
Dijkstras algoritm fungerar inte när en kant har negativ längd, som en väg som betalar dig en avgift i stället för att ta ut en. Det gör Bellman–Ford-algoritmen: den kontrollerar helt enkelt varje kant om och om igen tills inget blir bättre, och den kan till och med märka när en cykel får avstånden att sjunka för evigt. Klicka på en nod för att börja där och stega igenom varven. Tryck på Spela för att följa sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Varje kant är enkelriktad, som pilen visar, och talet på den är dess längd, som kan vara negativ. Klicka på en nod för att göra den till start; byt klicket till Mål och klicka på en annan nod för att se den kortaste vägen dit i slutet. Talet på varje nod är dess avstånd hittills. Kryssa i Lägg till en negativ cykel för att se hur Bellman–Ford hittar en. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Klicka på en nod för att göra den till start. Vill du se en väg i slutet, byt klicket till Mål och klicka på en annan nod.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
- Kryssa i Lägg till en negativ cykel för att se Bellman–Ford hitta en. Ny graf skapar en annan graf att prova.
Så fungerar Bellman–Ford
Ge starten avstånd 0 och alla andra noder oändligt. Gör sedan varv: i varje varv kontrolleras varje kant u → v en gång. Om u har ett avstånd och dist(u) plus kantens längd är kortare än dist(v), sänk dist(v) och kom ihåg u som vägen dit. Efter varv k är varje kortaste väg som använder högst k kanter känd. En kortaste väg besöker varje nod högst en gång, så den har högst n − 1 kanter, och n − 1 varv räcker alltid. Om ett helt varv inte ändrar något kan sökningen sluta tidigt.
Att hitta en negativ cykel
Om en cykels kanter tillsammans blir mindre än noll gör ett varv till runt den alltid en väg kortare, så det finns ingen kortaste väg alls. Bellman–Ford märker det: efter n − 1 varv borde ett varv till inte ändra något. Om en kant ändå kan relaxeras kan en negativ cykel nås från starten, och följer man de sparade noderna bakåt från den kanten hamnar man i den. I appen ritas cykeln i rött.
Ofta ställda frågor
Vad är Bellman–Ford-algoritmen?
En algoritm som hittar de kortaste vägarna från en start till alla andra noder i en graf vars kanter kan ha negativa längder. Den relaxerar varje kant i upprepade varv och rapporterar en negativ cykel om en sådan kan nås från starten.
Varför fungerar inte Dijkstras algoritm med negativa kanter?
Dijkstra gör en nods avstånd slutgiltigt så fort den är närmast i kön. En negativ kant som hittas senare kan fortfarande leda tillbaka till noden på en kortare väg, så det slutgiltiga avståndet kan bli fel. Bellman–Ford gör aldrig ett avstånd slutgiltigt i förtid; den fortsätter att kontrollera varje kant.
Varför n − 1 varv?
En kortaste väg behöver aldrig besöka en nod två gånger, så den har högst n − 1 kanter. Varje varv förlänger de kända kortaste vägarna med minst en kant, så efter n − 1 varv är alla hittade.
Hur snabb är Bellman–Ford?
Varje varv kontrollerar alla E kanter och det blir högst V − 1 varv, så arbetet växer med V × E. Det är långsammare än Dijkstras algoritm, och därför används Bellman–Ford när kanter kan vara negativa.
Skickas min graf någonstans?
Nej. Grafen skapas och genomsöks i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor