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 waarin de afstand tussen ieder tweetal verbonden punten van ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop de kortste afstand uit tot alle punten van . 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 als volgt berekend kan worden:

Zij de afstand tussen v en x, voor x een punt van .
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).

Het algoritme[bewerken]

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

: de verzameling van punten waarvan de kortste afstand tot berekend is
: de verzameling van punten waarnaar er al wel een pad bekend is vanuit , maar niet het kortste, of dit is nog niet vastgesteld.
: 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 , geïndiceerd met de punten v van . Voor elk punt wordt dit array door het algoritme dusdanig gevuld dat aan het eind geldt de lengte van het kortste pad van naar .

Initieel geldt

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

  1. Kies uit het punt 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 vanuit dat we tot nu toe gezien hebben. Ieder ander pad naar moet over lopen en is dus langer, omdat alle kanten een positieve lengte hebben.
  2. Omdat d(x) definitief is, verplaatsen we van naar . Voor alle punten die bereikbaar zijn vanuit en die nog niet in zitten, doen we het volgende:
    1. Zit nog niet in , dan voegen we het punt aan toe. Onze eerste schatting voor de afstand tussen en is dan -- deze waarde plaatsen we in d(z)
    2. Zit al wel in , 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 () en de lengte van het kortste pad naar dat we al gevonden hadden.

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

Algoritme in pseudocode[bewerken]

In pseudocode ziet het algoritme er als volgt uit:

 foreach v  V(G) do d(v) = 
 ;
 A := 
 d(a) := 0
 X := 
 foreach z : z   do 
   X := X  {z}
   d(z) := gew(,z)
 ; 
   /*
    * X en d zijn nu geïnitialiseerd
    */
 while not(X = ) do
   /*
    * X is nog niet leeg
    */
   y : (y  X)  (d(y) = MIN {d(y')|y'  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  {y}
   X := X{y} 
   /*
    * y is nu verplaatst van X naar A
    */
   foreach z: z  M_(y)  not (z  A) do 
     if not (z  X) then
        X := X  {z} 
        d(z) := d(y) + gew(y,z)
     else 
    /*
     * dus z  X
     */ 
        d(z) := MIN{d(z), d(y) + gew(y,z)}