Kortstepad-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959.[1] Gegeven een gewogen 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[bewerken]

Dijkstra's algorithm.svg

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 gewogen 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[bewerken]

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 het kortste, of dit is nog niet vastgesteld.
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[bewerken]

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
  1. Dijkstra, E., A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), blz. 269–271