Kortstepad-algoritme

een graaf-algoritme beschreven door Edsger Dijkstra in 1959
(Doorverwezen vanaf Kortstepadalgoritme)

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 om te bepalen wat het beste pad is voor een bepaald signaal.

De basisBewerken

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

Zij   de afstand tussen   en  , voor   een punt van  .
Zij  , de verzameling van punten   die direct verbonden zijn met w (via een tak van   naar  ).
Zij   het gewicht van de tak tussen twee direct met elkaar verbonden knopen   en  .
De afstand van   naar   is  , het minimum van de som van de afstand van   naar een punt   plus de directe afstand van dat punt naar  . 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   die direct verbonden zijn met   (via een tak van   naar  ).

Het algoritmeBewerken

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 (deze verzameling wordt niet bijgehouden in het algoritme)

Hiervoor geldt uiteraard dat  ,   en   hebben geen punten gemeen.

Daarnaast bestaat er een array  , geïndiceerd met de punten   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  ; dit is de eindwaarde van   voor dat punt. Immers,   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   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  
    2. Zit   al wel in  , dan passen we de schatting in   aan -- de nieuwe waarde is het minimum van de lengte van het nieuw-gevonden pad naar   ( ) 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   gevuld met de afstanden van   naar alle punten die vanuit dit beginpunt bereikbaar zijn. Is   oneindig voor een  , dan is dat punt   niet bereikbaar vanuit  .

Algoritme in pseudocodeBewerken

In pseudocode ziet het algoritme er als volgt uit:

 foreach   do  ;
 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       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)}

Hedendaagse toepassingenBewerken

Het algoritme wordt nog altijd veel toegepast in navigatieapparatuur, zoals de TomTom voor autoroutes of NavKid voor bootroutes. Daarbij wordt een wijziging toegepast; de afstand hoeft niet de echte afstand te zijn, maar kan ook worden uitgedrukt in tijd (voor de snelste route), in energieverbruik (de zuinigste route) of in straf/bonuspunten (voor bijvoorbeeld een mooie route, route met weinig afslagen, of een veilige route). Het principe van "afstand" blijft dan, maar er worden andere grootheden gebruikt.

Om het algoritme in de praktijk te kunnen gebruiken, zijn er enkele aanpassingen nodig, omdat niet de hele graaf (kaart) in het geheugen past. Ook kunnen er beperkingen zijn zoals de afmetingen van het voertuig of vaartuig, en bepaalde verkeersinformatie of stremmingen.