Dijkstras algoritm är en matematisk algoritm för att hitta den kortaste eller billigaste vägen från en given nod till alla andra noder i en viktad graf med positiva bågkostnader. Grafen kan vara riktad eller oriktad. Algoritmen har fått sitt namn efter Edsger Dijkstra, som utvecklade den år 1959. Den är en algoritm som systematiskt löser Bellmans ekvationer. Dijkstras algoritm är lite av ett specialfall när det kommer till algoritmer. I inledande steg är den att liknas vid en girig algoritm som alltid väljer den kortaste vägen mellan två noder. Den avslutas emellertid med att söka igenom hela den genomgångna grafen efter den totalt sett kortaste vägen, vilket gör algoritmen till ett mellanting mellan en girig algoritm och en algoritm som använder sig av dynamisk programmering.

Dijkstras algoritm
Pathfinding algorithm, grafalgoritm, girig algoritm, algoritm Redigera Wikidata
Uppkallad efterEdsger Dijkstra Redigera Wikidata
FörlagaBredd-först-sökning Redigera Wikidata
Upp­täc­ka­re eller upp­fin­na­reEdsger Dijkstra Redigera Wikidata
Upp­täckts­da­tum1959 Redigera Wikidata
Lösershortest path problem, pathfinding, single-source shortest path problem Redigera Wikidata
Tids­komp­lex­i­tet i värsta fall,  Redigera Wikidata

Lösningar till problemet med den billigaste vägen behövs inom många områden, exempelvis inom ruttplanering för att hitta den kortaste vägen när transportsträckor läggs ut. Den används också inom webbaserade reseplanerare för kollektivtrafik för att hitta snabbaste vägen.[1]

Algoritmbeskrivning

redigera

Beskrivningen nedan löser problemet att finna den billigaste vägen från startnoden   till terminalnoden   där   beskriver kostnaden på bågen  . Låt   representera den kortaste vägen till nod   och   dess föregångare.

  1. Sätt  . För alla andra noder, sätt  .
  2. Finn den nod   med lägst nodpris   som ännu inte är avsökt.
  3. Undersök varje båge   som utgår från nod  . Om den representerar en billigare väg till nod  , det vill säga att  , uppdateras värdena för nod   med   och  .
  4. Gå till steg 2 om inte alla noder är avsökta.

När algoritmen är färdig återfinns den billigaste vägen genom att avläsa föregångaren   till slutnoden, sedan den nodens föregångare, och så vidare tills startnoden påträffas.

Exempel

redigera
 
Exempel av Dijkstras algoritm med en viktad oriktad graf.

Bilden visar ett exempel av Dijkstras algoritm, där de olika variablernas värden visas under körning. Den optimala vägen från nod a till nod b beräknas. Initialt sätts nodpriserna till   för alla noder utom startnoden, som får nodpris  . För varje nod beräknas de närliggande nodpriserna, och noden markeras därefter som avsökt genom den röda fyllningen.

När slutnoden b avsöks har den optimala vägen beräknats.

Varianter

redigera

Dijkstras algoritm ger inte alltid en lösning av problemet när vissa bågkostnader är negativa. Bellman-Fords algoritm löser detta genom att i steg 3 markera nod   som icke avsökt. Med icke-negativa bågkostnader är   redan icke avsökt.

Efter att nod   i algoritmbeskrivningen markerats som avsökt har alla avsökta noder fått permanenta nodpriser, som representerar priset av den billigaste vägen från startnoden dit. Varje ännu ej avsökt nod har ett nodpris, som är priset på den billigaste vägen från startnoden dit genom de redan avsökta noderna. Denna egenskap behålls i varje iteration av algoritmen. När alla noder är markerade som avsökta är alltså även varje nodpris det optimala.

Att egenskapen behålls i varje iteration kan bevisas genom att antaga att den nod   som väljs att avsöka har nodpriset   som inte är optimalt. Då skulle det finnas en väg genom de ej avsökta noderna som är billigare. Kalla en av dessa noder för nod  . Eftersom alla bågar i grafen är positiva (annars är Dijkstras algoritm inte applicerbar) måste priset för billigaste vägen från nod   till nod   vara positiv. Billigaste vägen från startnoden till nod   är nodpriset  . Det betyder att vägen från startnoden till nod   är dyrare än vägen till nod  .

Från metoden med vilken vi valde nod   ser vi dock att nodpriset   inte är lägre än nodpriset  . Där ligger en motsägelse. Alltså var det ursprungliga antagandet felaktigt, och nodpriset   är optimalt.

Komplexitet

redigera

Om man implementerar prioritetskön med hjälp av en Fibonacci heap så har algoritmen tidskomplexiteten  , där   är antalet noder och   är antalet vägar i grafen.

Implementering

redigera

Följande program är en implementering av Dijkstras algoritm i pseudokod.

   DIJKSTRA (Graf G, startnod s)
       // Vi initierar alla noder i grafen.
       // Billigaste vägen (avståndet) är oändligt
       // och föregående nod är odefinierad.
       för iNoder(G) gör
           avstånd[i] = OÄNDLIGT
           föregångare[i] = NULL
       // Avståndet till startnoden är 0.
       avstånd[s] = 0
       // Markera startnoden som avsökt.
       Avsökt( s )
       medan inte alla noder avsökta gör
           // Finn den ej avsökta nod som har lägst nodpris
           // tills alla är avsökta.
           i = Minimum( ej avsökta noder )
           för j ∈ närliggande(i) gör
               // Undersök om det finns en billigare väg
               // via nod i till närliggande noder.
               om avstånd[j] > avstånd[i] + kostnad(i, j) gör
                   avstånd[j] = avstånd[i] + kostnad(i, j)
                   föregångare[j] = i
           Avsökt( i )

Referenser

redigera
  1. ^ Computerphile (4 januari 2017). ”Dijkstra's Algorithm - Computerphile”. https://www.youtube.com/watch?v=GazC3A4OQTE. Läst 18 januari 2017.