Kortstepad-algoritme

Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959.^[1] Gegeven een gewogen graaf ${\displaystyle G}$ waarin de afstand tussen ieder tweetal verbonden punten van ${\displaystyle G}$ ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop ${\displaystyle g_{b}\in G}$ de kortste afstand uit tot alle punten van ${\displaystyle G}$. Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie.

Basis

Het algoritme is gebaseerd op de opmerking dat de 'afstand', de lengte van het kortste pad, tussen ieder tweetal punten ${\displaystyle v}$ en ${\displaystyle w}$ van een gewogen graaf ${\displaystyle G}$ als volgt berekend kan worden:

Zij ${\displaystyle d(x)}$ de afstand tussen ${\displaystyle v}$ en ${\displaystyle x}$, voor ${\displaystyle x}$ een punt van ${\displaystyle G}$.

Zij ${\displaystyle N_{w}=\{y\in G\mid y\rightarrow w\}}$, de verzameling van punten ${\displaystyle y}$ die direct verbonden zijn met ${\displaystyle w}$, via een tak van ${\displaystyle y}$ naar ${\displaystyle w}$.

Zij ${\displaystyle gew(y,w)}$ het gewicht van de tak tussen twee direct met elkaar verbonden knopen ${\displaystyle y}$ en ${\displaystyle w}$.

De afstand van ${\displaystyle v}$ naar ${\displaystyle w}$ is ${\displaystyle d(w)=\min\{d(y)+gew(y,w)\mid y\in N_{w}\}}$, het minimum van de som van de afstand van ${\displaystyle v}$ naar een punt ${\displaystyle y\in N}$ plus de directe afstand van dat punt naar ${\displaystyle w}$. Oftewel 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 ${\displaystyle M_{v}=\{y\in G\mid v\rightarrow y\}}$, de verzameling van punten ${\displaystyle y}$ die direct verbonden zijn met ${\displaystyle v}$, via een tak van ${\displaystyle v}$ naar ${\displaystyle y}$.

Algoritme

Het algoritme gaat verder door op de basis van hierboven. Het algoritme verdeelt de punten van ${\displaystyle G}$ in drie verzamelingen:

${\displaystyle A}$: de verzameling van punten waarvan de kortste afstand tot ${\displaystyle g_{b}}$ berekend is

${\displaystyle X}$: de verzameling van punten waarnaar er al wel een pad bekend is vanuit ${\displaystyle g_{b}}$, maar niet het kortste, of dit is nog niet vastgesteld.

${\displaystyle V=G-A-X}$: deze verzameling wordt in het algoritme niet bijgehouden

Hiervoor geldt uiteraard dat ${\displaystyle A\cap X=\emptyset }$, ${\displaystyle A}$ en ${\displaystyle X}$ hebben geen punten gemeen.

Daarnaast bestaat er een array ${\displaystyle d(v)}$, geïndiceerd met de punten ${\displaystyle v}$ van ${\displaystyle G}$. Voor elk punt ${\displaystyle g\in G}$ wordt dit array door het algoritme dusdanig gevuld dat aan het eind geldt ${\displaystyle d(g)=}$ de lengte van het kortste pad van ${\displaystyle g_{b}}$ naar ${\displaystyle g}$.

Initieel geldt

• ${\displaystyle A=\{g_{b}\}}$
• ${\displaystyle X=M_{g_{b}}}$
• ${\displaystyle d(g_{b})=0}$
• ${\displaystyle \forall {g\in X}:d(g)=gew(g_{b},g)}$
• ${\displaystyle \forall {g\in V(G)-X-A}:d(g)=\infty }$

Het algoritme herhaalt nu de volgende stappen totdat ${\displaystyle X}$ de lege verzameling wordt (op dat moment zijn er geen bereikbare punten meer over), vanuit ${\displaystyle g_{b}}$:

1. Kies uit ${\displaystyle X}$ het punt ${\displaystyle x}$ met de minimale waarde van ${\displaystyle d(x)}$; dit is de eindwaarde van ${\displaystyle d(x)}$ voor dat punt. Immers, ${\displaystyle d(x)}$ heeft de waarde van de lengte van het kortste pad naar ${\displaystyle x}$ vanuit ${\displaystyle g_{b}}$ dat we tot nu toe gezien hebben. Ieder ander pad naar ${\displaystyle x}$ moet over ${\displaystyle x}$ lopen en is dus langer, omdat alle kanten een positieve lengte hebben.
2. Omdat ${\displaystyle d(x)}$ definitief is, verplaatsen we ${\displaystyle x}$ van ${\displaystyle X}$ naar ${\displaystyle A}$. Voor alle punten ${\displaystyle z}$ die bereikbaar zijn vanuit ${\displaystyle x}$ en die nog niet in ${\displaystyle A}$ zitten, doen we het volgende:
   1. Zit ${\displaystyle z}$ nog niet in ${\displaystyle X}$, dan voegen we het punt aan ${\displaystyle X}$ toe. Onze eerste schatting voor de afstand tussen ${\displaystyle g_{b}}$ en ${\displaystyle z}$ is dan ${\displaystyle d(x)+gew(x,z)}$ -- deze waarde plaatsen we in ${\displaystyle d(z)}$
   2. Zit ${\displaystyle z}$ al wel in ${\displaystyle X}$, dan passen we de schatting in ${\displaystyle d(z)}$ aan -- de nieuwe waarde is het minimum van de lengte van het nieuw-gevonden pad naar ${\displaystyle z}$ (${\displaystyle d(x)+gew(x,z)}$) en de lengte van het kortste pad naar ${\displaystyle z}$ dat we al gevonden hadden.

Zodra dit algoritme afloopt (en dat doet het, want ${\displaystyle V(G)}$ is eindig en iedere stap verplaatst een element van ${\displaystyle X}$ naar ${\displaystyle A}$), dan is ${\displaystyle d(v)}$ gevuld met de afstanden van ${\displaystyle g_{b}}$ naar alle punten die vanuit dit beginpunt bereikbaar zijn. Is ${\displaystyle d(w)}$ oneindig voor een ${\displaystyle w\in V(G)}$, dan is dat punt ${\displaystyle w}$ niet bereikbaar vanuit ${\displaystyle g_{b}}$.

Algoritme in pseudocode

In pseudocode ziet het algoritme er als volgt uit:

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

Bewijs

De correctheid van het algoritme kan aangetoond worden aan de hand van wiskundige inductie. ^[2][3]

Concreet moet er aangetoond worden dat de afstanden ${\displaystyle d(v)}$ die het algoritme berekent effectief de afstanden (volgens het kortste pad) zijn tussen het startknooppunt ${\displaystyle g_{b}}$ en de knoop ${\displaystyle v}$. Die afstanden worden vastgelegd wanneer knoop ${\displaystyle v}$ aan de verzameling ${\displaystyle A}$ (de verzameling van punten waarvan de kortste afstand tot ${\displaystyle g_{b}}$ berekend is). Merk op dat, eens ${\displaystyle v}$ aan ${\displaystyle A}$ is toegevoegd, de afstand ${\displaystyle d(v)}$ niet meer gewijzigd wordt en er ook geen kortere afstand meer gevonden kan worden binnen de beschouwde graaf. Dit laatste is een rechtstreeks gevolg van de manier waarop het algoritme opgebouwd is en omdat alle gewichten ${\displaystyle w(x,y)}$ van takken tussen knopen ${\displaystyle x}$ en ${\displaystyle y}$ positief zijn (een van de basisaannames van het algoritme). Merk op dat de notatie ${\displaystyle \delta (y)}$ verderop expliciet wordt ingevoerd om het onderscheid te maken met de finale (en correcte) afstand ${\displaystyle d(y)}$ die het algoritme uiteindelijk zal uitvoeren.

Basisstap van de wiskundige inductie

Het bewijs wordt nu geleverd door wiskundige inductie. In het basisgeval wordt een graaf beschouwd met een enkele knoop ${\displaystyle s}$. Door de opbouw van het algoritme zal deze knoop bij de eerste iteratie aan ${\displaystyle A}$ toegevoegd worden, met ${\displaystyle d(s)=0}$. In het basisgeval is het algoritme dus correct.

Inductiestap

Vermits het basisgeval correct is, kan nu aangenomen worden dat voor alle knopen ${\displaystyle y}$ die al in de verzameling ${\displaystyle A}$ zitten, de berekende afstand ${\displaystyle d(y)}$ effectief overeenkomt met de gezochte kortste afstand (lengte van een kortste pad tussen ${\displaystyle g_{b}}$ en ${\displaystyle y}$). Er moet nu bewezen worden dat, wanneer een volgende knoop ${\displaystyle x}$ wordt toegevoegd aan de verzameling ${\displaystyle A}$, de berekende afstand ${\displaystyle d(x)=gew(g_{b};x)}$ effectief de lengte is van een kortste pad. Anders gezegd: in deze inductiestap wordt bewezen dat het algoritme de correcte afstand berkend heeft op het moment dat die afstand finaal wordt vastgelegd (ofwel wanneer de knoop aan verzameling ${\displaystyle A}$ wordt toegevoegd).^[3]

Beschouw nu een kortste pad ${\displaystyle p}$ van ${\displaystyle g_{b}}$ naar ${\displaystyle x}$ (nog steeds de volgende knoop die aan ${\displaystyle A}$ zal toegevoegd worden omdat die van alle knopen in ${\displaystyle X}$ het kleinste afstandslabel ${\displaystyle \delta (x)}$ bezit). Beschouw op dit kortste pad de knoop ${\displaystyle z}$ die het dichtst bij ${\displaystyle x\not \in A}$ ligt en waarvoor ${\displaystyle \delta (z)=d(z)}$. Merk op dat ${\displaystyle z}$ sowieso gedefinieerd is (er zal namelijk altijd één knoop, zijnde ${\displaystyle g_{b}}$ bestaan waar de voorwaarde voldaan is). Beschouw nu twee gevallen.

Indien ${\displaystyle z=x}$, dan is ${\displaystyle x\in A}$. Er geldt dan dat ${\displaystyle \delta (x)=d(x)}$. Omdat ${\displaystyle x}$ nu wordt toegevoegd aan ${\displaystyle A}$, terwijl ${\displaystyle \delta (x)=\delta (z)=d(x)}$, levert het algoritme een correcte uitkomst. In dit geval is de correcte werking van het algoritme dus bewezen.

In het logische geval is ${\displaystyle z\neq x}$. Herinner dat ${\displaystyle x\in X}$ en bovendien ${\displaystyle x\not \in A}$ en ten derde ${\displaystyle x}$ de volgende knoop is die aan ${\displaystyle A}$ wordt toegevoegd door het algoritme. Indien ${\displaystyle z\neq x}$, dan bestaat er nog een knoop ${\displaystyle z'\neq z}$ die op het kortste pad ${\displaystyle p}$ ligt en daarop vlak na ${\displaystyle z}$ op het pad ligt. In dit geval beschouwen we dus een situatie waarbij ${\displaystyle \delta (x)\neq d(x)}$, anders gezegd een situatie waarin het algoritme niet werkt. Merk op dat deelpaden van korste paden in de grafentheorie zelf ook kortste paden zijn. Het deel van ${\displaystyle p}$ tussen ${\displaystyle z}$ en ${\displaystyle g_{b}}$ bezit dus een gewicht ${\displaystyle d(z)}$. Omdat bovendien alle takken een positief gewicht hebben, moet bovendien gelden: ${\displaystyle d(z)\leq d(x)}$. Door de constructie van het algoritme kan deze ongelijkheid bovendien uitgebreid worden tot ${\displaystyle d(z)\leq d(x)\leq \delta (x)}$. Het tweede luik van de ongelijkheid oogt triviaal, maar kan ook inductief bewezen worden.^[3]

De vorige ongelijkheid kan terug opgesplitst worden in twee gevallen. In het eerste is ${\displaystyle d(x)=\delta (x)=d(z)}$. De ongelijkheden worden vervangen door gelijkheden, waardoor de correctheid van het algoritme terug bewezen is. Beschouw nu het geval waarin ${\displaystyle d(z)<\delta (x)}$. Dit is dus het geval waarin een knoop aan ${\displaystyle A}$ zou toegevoegd worden met een verkeerd voorspelde afstand. Dit is niet mogelijk, zoals blijkt uit volgende contradictie. ${\displaystyle x}$ is gekozen als de knoop die als volgende aan ${\displaystyle A}$ toegevoegd wordt omdat het bijhorende afstandslabel ${\displaystyle \delta (x)}$ het kleinst is van alle knopen in ${\displaystyle X}$ is. Uit die redenering volgt dus dat ${\displaystyle z}$ niet langer in ${\displaystyle F}$ kan zitten, omdat anders ${\displaystyle x=z}$ door het algoritme zou geselecteerd worden. Aangezien ${\displaystyle z\in A}$, is ook het afstandslabel ${\displaystyle \delta (z')}$ in een vorige stap bijgewerkt volgens de logica van het algoritme. Derhalve geldt: ${\displaystyle \delta (z')\leq d(z)+gew(z,z')=d(z')}$. Omdat ${\displaystyle z}$ en ${\displaystyle z'}$ op eenzelfde kortste pad ${\displaystyle p}$ liggen tussen ${\displaystyle g_{b}}$ en ${\displaystyle x}$ (en daardoor dus ook op een kortste pad tussen ${\displaystyle g_{b}}$ en ${\displaystyle z'}$), moet ${\displaystyle \delta (z')=d(z')}$. Dit is echter strijdig met de definitie van ${\displaystyle z}$ als de knoop die het dichtst bij ${\displaystyle x}$ ligt en voldoet aan ${\displaystyle \delta (z)=d(z)}$. Dit impliceert dat de aanname ${\displaystyle d(z)<\delta (x)}$ niet correct was, en dat ${\displaystyle d(z)=\delta (x)=d(x)}$ moet zijn. Hiermee is de correctheid van het algoritme finaal bewezen.