Kortstepadalgoritme

Het kortstepadalgoritme (ook bekend als Dijkstra's algoritme) is een graaf-algoritme bedacht door Edsger Dijkstra. 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 de kortste afstand uit tot alle punten van G. Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie.

[bewerk] 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 de afstand tussen v en x, voor x een punt van G.

Zij , de verzameling van punten y die direct verbonden zijn met w (via een tak van y naar w).

Zij het gewicht van de tak tussen twee direct met elkaar verbonden knopen y en w.

De afstand van v naar w is , 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 , de verzameling van punten y die direct verbonden zijn met v (via een tak van v naar y).

[bewerk] Het algoritme

Het algoritme is eigenlijk een veralgemening 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 en X hebben geen punten gemeen.

Daarnaast bestaat er een array d(v), geïndiceerd met de punten v van G. Voor elk punt 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}
• 
• d(g_b) = 0
• 
• 

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 , dan is dat punt w niet bereikbaar vanuit g_b.

[bewerk] Algoritme in pseudocode

In pseudocode ziet het algoritme er als volgt uit:

 forall v IN V(G) do d(v) = infinity llarof
 ;
 A := {g_b}
 ;
 d(a) := 0
 ;
 X := empty_set
 ;
 forall z : z IN M_(g_b) do 
   X := X UNION {z}
   ;
   d(z) := gew(g_b,z)
 llarof
 ; {X en d zijn nu geïnitialiseerd}
 while not(X = empty_set) 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 UNION {y}
   ;
   X := X - {y}
   ; {y is nu verplaatst van X naar A}
   forall z: z IN M_(y) AND not (z IN A) do 
     if not (z IN X) then
        begin
           X := X UNION {z} 
           d(z) := d(y) + gew(y,z)
        end
     else {dus z in X} d(z) := MIN{d(z), d(y) + gew(y,z)}
     fi
   llarof
 elihw