title: Kortstepad-algoritme
text: Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. 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 
  
  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 algoritme 
  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 :
  
   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.
   Omdat  definitief is, verplaatsen we  van  naar . Voor alle punten  die bereikbaar zijn vanuit  en die nog niet in  zitten, doen we het volgende:
   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 
   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 pseudocode 
  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 toepassingen
  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.
  
  Algoritme