Kortstepad-algoritme

Het kortstepadalgoritme, 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 := gb
 d(a) := 0
 X := $\emptyset$
 foreach z : z $\in$ $M_{(g_b)}$ do 
   X := X $\cup$ {z}
   d(z) := gew(gb,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)}

Referenties