Kortstepad-algoritme

Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. Gegeven een gerichte graaf $G$ waarin de afstand tussen ieder tweetal verbonden punten van $G$ ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop $g_b \in G$ de kortste afstand uit tot alle punten van $G$. Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie.

De basis

Het algoritme is gebaseerd op de opmerking dat de afstand (de lengte van het kortste pad) tussen ieder tweetal punten v en w van een gerichte graaf $G$ als volgt berekend kan worden:

Zij $d(x) \!$ de afstand tussen v en x, voor x een punt van $G$.

Zij $N_w = \{y \in G | y \rightarrow w\}$, de verzameling van punten y die direct verbonden zijn met w (via een tak van y naar w).

Zij $gew(y,w) \!$ het gewicht van de tak tussen twee direct met elkaar verbonden knopen y en w.

De afstand van v naar w is $d(w) = min \{d(y) + gew(y,w) | y \in N_w\}$, het minimum van de som van de afstand van v naar een punt y in N plus de directe afstand van dat punt naar w. Oftewel - weinig verrassend - als de som van alle directe afstanden in een pad minimaal is, dan is de totale lengte van dat pad (die som dus) minimaal.

Verder definiëren we $M_v = \{y \in G | v \rightarrow y\}$, de verzameling van punten y die direct verbonden zijn met v (via een tak van v naar y).

Het algoritme

Het algoritme is eigenlijk een veralgemenisering van de basis van hierboven. Het algoritme verdeelt de punten van $G$ in drie verzamelingen:

$A$: de verzameling van punten waarvan de kortste afstand tot $g_b$ berekend is

$X$: de verzameling van punten waarnaar er al wel een pad bekend is vanuit $g_b$, maar niet noodzakelijk het kortste

$V(G) - A - X$: de overige punten van V (deze verzameling wordt niet bijgehouden in het algoritme en heeft dus geen naam)

Hiervoor geldt uiteraard dat $A \cap X = \emptyset$, A en X hebben geen punten gemeen.

Daarnaast bestaat er een array $d(v)$, geïndiceerd met de punten v van $G$. Voor elk punt $g \in G$ wordt dit array door het algoritme dusdanig gevuld dat aan het eind geldt $d(g) =$ de lengte van het kortste pad van $g_b$ naar $g$.

Initieel geldt

• $A = \{g_b\}$
• $X = M_{g_b}$
• $d(g_b) = 0$
• $\forall {g \in X} : d(g) = gew(g_b,g)$
• $\forall {g \in V(G) - X - A} : d(g) = \infty$

Het algoritme herhaalt nu de volgende stappen totdat $X$ de lege verzameling wordt (op dat moment zijn er geen bereikbare punten meer over), vanuit $g_b$:

1. Kies uit $X$ het punt $x$ met de minimale waarde van d(x); dit is de eindwaarde van d(x) voor dat punt. Immers, d(x) heeft de waarde van de lengte van het kortste pad naar $x$ vanuit $g_b$ dat we tot nu toe gezien hebben. Ieder ander pad naar $x$ moet over $x$ lopen en is dus langer, omdat alle kanten een positieve lengte hebben.
2. Omdat d(x) definitief is, verplaatsen we $x$ van $X$ naar $A$. Voor alle punten $z$ die bereikbaar zijn vanuit $x$ en die nog niet in $A$ zitten, doen we het volgende:
   1. Zit $z$ nog niet in $X$, dan voegen we het punt aan $X$ toe. Onze eerste schatting voor de afstand tussen $g_b$ en $z$ is dan $d(x) + gew(x,z)$ -- deze waarde plaatsen we in d(z)
   2. Zit $z$ al wel in $X$, dan passen we de schatting in d(z) aan -- de nieuwe waarde is het minimum van de lengte van het nieuw-gevonden pad naar z ($d(x) + gew(x,z)$) en de lengte van het kortste pad naar $z$ dat we al gevonden hadden.

Zodra dit algoritme afloopt (en dat doet het, want $V(G)$ is eindig en iedere stap verplaatst een element van $X$ naar $A$), dan is d(v) gevuld met de afstanden van $g_b$ naar alle punten die vanuit dit beginpunt bereikbaar zijn. Is d(w) oneindig voor een $w \in V(G)$, dan is dat punt w niet bereikbaar vanuit $g_b$.

Algoritme in pseudocode

In pseudocode ziet het algoritme er als volgt uit:

 foreach v $\in$ V(G) do d(v) = $\infty$
 ;
 A := $g_b$
 d(a) := 0
 X := $\emptyset$
 foreach z : z $\in$ $M_{(g_b)}$ do 
   X := X $\cup$ {z}
   d(z) := gew($g_b$,z)
 ; 
   /*
    * X en d zijn nu geïnitialiseerd
    */
 while not(X = $\emptyset$) do
   /*
    * X is nog niet leeg
    */
   y : (y $\in$ X) $\and$ (d(y) = MIN {d(y')|y' $\in$ X}
   /*
    * y is dus het element van X met de laagste waarde van d(v) -- dit is de definitieve 
    * waarde van d(y)
    */
   A := A $\cup$ {y}
   X := X$\setminus${y} 
   /*
    * y is nu verplaatst van X naar A
    */
   foreach z: z $\in$ M_(y) $\and$ not (z $\in$ A) do 
     if not (z $\in$ X) then
        X := X $\cup$ {z} 
        d(z) := d(y) + gew(y,z)
     else 
    /*
     * dus z $\in$ X
     */ 
        d(z) := MIN{d(z), d(y) + gew(y,z)}

Bronnen, noten en/of referenties