Problem: Givet en graf (riktad eller oriktad) där varje båge har en viss längd, och två noder s och t, hitta den kortaste vägen från s till t.

Att hitta kortaste vägen mellan två punkter är ett problem som givetvis uppkommer i transportsammanhang men även inom t.ex. bildbehandling. På tävlingar kommer säkert inte problemet i ren form, men det skulle kunna vara en del av en större lösning. Lyckligtvis är problemet lätt att lösa. Den beskrivna metoden kallas för Dijkstra's algoritm.

Först ett specialfall: alla bågar har längden 1. Då ges lösningen direkt av bredden-först-sökning (BFS) , med noderna som situationer och s som startsituation. Dijkstra's algoritm är väldigt lik BFS, och därför förutsätts här att du vet hur denna sökning fungerar.

Antag att du är mitt i BFS-sökning av en graf. Du tar fram en nod A markerad med 3 "drag" ur kön. I detta sammanhang betyder detta att det kortaste avståndet mellan s och A är 3. Sedan gör du alla möjliga drag, i detta fall undersöker du alla intilliggande noder. Om någon nod B inte redan är markerad, innebär det att du automatiskt vet att avståndet från s till B är 4, för om avståndet vore <= 3 skulle noden redan vara markerad eftersom alla 3-noder hittas innan 4-noderna. (Däremot kan det finnas någon annan väg som också ger avståndet 4, men då spelar det ju ingen roll vilken vi väljer.) Vi kan också lugnt placera B sist i kön eftersom den då hamnar efter alla 3-noder och före alla framtida 5-noder.

Om bågarna inte har längden 1 blir det lite annorlunda. Vi kan inte längre vara säkra på att vi direkt har hittat kortaste avståndet till B. Om t.ex. längden av bågen A -B = 3, blir ju avståndet från s till B = 6. Men kanske hittar vi strax efteråt en annan 3-nod som också har en båge till B med längden 2. Då blir det den kortaste vägen från s till B (avstånd 5). Tydligen är det så att när vi först hittar en väg till B är det en möjlig kortaste väg, men vi kan inte veta säkert. När kan vi bli säkra?

Antag att du markerar med svart de noder som du är säker på kortaste vägen till, i detta exempel s med avståndet 0 samt A och C med avståndet 3. Titta nu på alla bågar som kopplar ihop en svart nod med en vit (A-B, C-B ,  C-D). Välj den av dessa som ger det kortaste avståndet från s till den vita noden (C-B ger avståndet 3 + 2 = 5 från s till B) och markera B som svart med avståndet 5. Vi kan nämligen vara säkra på att det inte finns en kortare väg till B, eftersom en sådan  väg skulle gå från någon av de svarta noderna till en annan vit och då automatiskt bli längre. För varje nod vi markerar med svart är vi ett steg närmare lösningen. I exemplet ovan blir ordningen: B (avstånd 5),   F (6),   D (7),   E (10),   t (12)

Ett enkelt sätt att hålla reda på de "svart-vita" bågarna visas i nedanstående algoritm. Varje gång man svartmarkerar en nod, undersöker man dess vita grannar för att se om det går att hitta bättre vägar till dessa via den nu svartmarkerade noden. Första gången en nod påträffas handlar det ju om att det finns en väg dit överhuvudtaget, men detta specialfall behöver man inte bry sig om om man sätter alla avstånd i början till ett stort värde (helst oändligheten).
Exempel:
När F hittas sätts dist[t] till 6 + 9 = 15, eftersom 6 + 9 < 1000000 (som var ursprungsvärdet för dist[t] ).
Däremot behåller dist[D] värdet 7, eftersom 6 + 3 inte är < 7
När E hittas sätts dist[t] till 10 + 2 = 12 eftersom 10 + 2 < 15

Det effektivaste sättet att välja det minsta dist-värdet bland de vita noderna, är att spara dist-värdena i en prioritetskö, som implementeras med en heap . Oftast räcker det dock att ha en array som man letar igenom varje gång. Algoritmen blir ändå bara O(E*V) där V är antalet noder och E är antalet bågar.

Det som blir enkelt när man använder en array är just när en bättre väg hittas, alltså när ett dist-värde måste uppdateras. Om man har en array är det bara att ändra värdet på dist[v]. Eftersom man sedan letar igenom alla noder för att ta den minsta kommer man att hitta v ifall v har det minsta dist-värdet. Om man använder en prioritetskö (heap) utnyttjar man heapens struktur för att bara behöva tiden O(log V) varje gång man tar den nod med minst dist-värde. Därför måste man uppdatera heapen varje gång ett dist-värde minskas, den noden ska flyttas fram i kön. Detta görs genom att ha någon slags "pekare" från noden till heapen så att det lätt går att hitta dess plats. Vet man nodens plats är det bara att göra en INSERT -liknande procedur som flyttar noden uppåt i heapen (framåt i kön). Det blir alltså lite krångligare, men det kan vara nödvändigt i problem med många noder, eftersom algoritmen med heap blir O(E*log V).

Shortest_Path(s, t)
    black[1..numNodes] := false
    dist[1..numNodes] := 1000000  Stort värde - betecknar ej hittad nod
    dist[s] := 0  Startnoden har avståndet 0

    while (vita hittade noder existerar) do
        u := den vita nod (d.v.s. black[u] = false) som har minst dist-värde
        black[u] := true  Markera u med svart
        for e := (alla bågar från u) do
            v := den andra noden till båge e
            if (not black[v]) and (dist[u] + length[e] < dist[v]) then
                dist[v] := dist[u] + length[e]        En bättre väg till v är hittad
                Flytta v framåt i prioritetskön       Om heap används

    if dist[t] = 1000000 then
        **** Omöjligt att komma från s till t ****
    else
        **** Kortaste vägen har längden dist[t] ****
 

Alla kortaste vägar

Ibland vill man inte bara veta kortaste vägen mellan s och t, eller mellan s och alla andra noder (detta ges också av Dijkstra's algoritm), utan mellan alla kombinationer av två noder. Man kan givetvis köra Dijkstra's algoritm numNodes gånger med olika noder som startnod, men det finns en algoritm som är ännu kortare att skriva. Den är så enkel att det till och med kan löna sig att använda den för att hitta bara en kortaste väg, om man vet att man har gott om exekveringstid. Komplexiteten är O(n^ 3) med avseende på antalet noder.

Tillbaka