Dijkstras algoritm
Din ruttplanerare vet den snabbaste vägen från din dörr till nästan var som helst. Kärnan i den idén är en algoritm som Edsger Dijkstra kom på på ungefär tjugo minuter 1956: väx utåt från starten och gör alltid den närmaste platsen klar först.
Idén
Tänk dig städer förbundna med vägar av olika längd. Frågan är: vilken är den kortaste vägen från min stad till var och en av de andra? Bredden-först-sökning svarar på det när varje väg räknas lika, men här kan en rutt med fler vägar vara kortare. Dijkstras algoritm håller för varje stad reda på det kortaste avstånd som hittats hittills och låter ett område av städer vars avstånd är säkert växa, genom att alltid lägga till den närmaste stad som inte är säker än.
Steg för steg
Ge starten avstånd 0 och alla andra noder oändligt. Lägg starten i en prioritetskö, en kö som alltid lämnar ut noden med minst avstånd. Ta den noden; dess avstånd är nu slutgiltigt. För varje granne som inte är slutgiltig, räkna ut avståndet via den här noden: nodens avstånd plus kantens längd. Är det kortare än grannens avstånd hittills, sänk det, spara den här noden som vägen dit och lägg grannen i kön. Det kallas att relaxera en kant. Upprepa tills kön är tom, eller tills målet tas från den.
Ett exempel
Ta kanterna A–B med längd 4, A–C 1, B–C 2, B–D 1, C–D 5 och D–E 3, och börja i A. Att ta A ger B avstånd 4 och C avstånd 1. C är närmast, så den är slutgiltig på 1; via C sjunker B till 1 + 2 = 3 och D får 1 + 5 = 6. Nu är B närmast, slutgiltig på 3, och via B sjunker D till 3 + 1 = 4. D är slutgiltig på 4 och ger E 4 + 3 = 7. Den kortaste vägen från A till E är alltså A → C → B → D → E, längd 7, trots att A → B → D → E använder färre kanter och har längd 8.
Varför den är korrekt
Anta att nod X är den närmaste i kön, på avstånd d. Varje annan väg från starten till X måste någon gång lämna området av slutgiltiga noder, och den första nod den når utanför området finns i kön, så den ligger redan minst d bort. Resten av vägen kan inte göra den kortare, eftersom ingen kant är negativ. Alltså är d det kortaste avståndet till X. Med en negativ kant håller resonemanget inte; då används i stället Bellman–Ford-algoritmen, som relaxerar varje kant om och om igen.
Historia och användning
Edsger W. Dijkstra utformade algoritmen 1956 för att visa upp en ny dator, ARMAC i Amsterdam, genom att hitta vägar mellan nederländska städer, och publicerade den 1959. Samma idé, med en smartare kö, används i ruttplanerare och i internets routningsprotokoll som OSPF och IS-IS, som räknar ut den kortaste vägen för data mellan routrar. A*-sökning lägger till en gissning av avståndet som återstår, så att den kan styra mot målet och titta på färre noder.
Utforska den
Öppna appen och tryck på Steg. Talen på kanterna är deras längder, och talet på varje nod är dess avstånd hittills. Noder i kön är blå, slutgiltiga noder gröna, och kön under grafen listar dem med sina avstånd, närmaste först. Håll utkik efter stunderna när ett avstånd sjunker för att en väg som ser längre ut visar sig vara kortare, och välj ett mål för att se sökningen stanna så snart målet är slutgiltigt.
Ofta ställda frågor
Vilken tidskomplexitet har Dijkstras algoritm?
Det beror på prioritetskön. Med en enkel lista är den O(V²) för V noder; med en binär heap O((V + E) log V) för E kanter; med en Fibonacci-heap O(E + V log V), som Michael Fredman och Robert Tarjan visade 1984.
Klarar Dijkstras algoritm negativa kantvikter?
Nej. Den förutsätter att en nods avstånd inte kan förbättras när noden väl är den närmaste i kön, och det kan en negativ kant bryta. Använd Bellman–Ford-algoritmen för grafer med negativa kanter.
Hittar Dijkstras algoritm vägen till varje nod?
Ja. Körd till slutet ger den det kortaste avståndet från starten till varje nod som kan nås, och de sparade noderna bildar ett träd av kortaste vägar. Att stanna tidigt när målet är slutgiltigt sparar arbete när du bara behöver en väg.
Hur hänger Dijkstras algoritm ihop med A*?
A*-sökning är Dijkstras algoritm med en ledtråd: den ordnar kön efter avståndet hittills plus en uppskattning av avståndet som återstår, till exempel fågelvägen på en karta. Med en bra uppskattning hittar den samma kortaste väg och tittar på betydligt färre noder.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova Dijkstras algoritm