Beheer

Vind het kortste pad

Chris Kettenis 2021-02-01 12:44:38
Vind het kortste pad van herkomst naar bestemming.

Als de kosten op het netwerk zijn gezet, kan er op zoek worden gegaan naar de route over het netwerk met de laagste kosten van de herkomst van de reis naar de bestemming van de reis. Hiervoor gebruikt BIVAS een implementatie van Dijkstra's kortste pad algoritme (zie ook Dijkstra's algoritme op wikipedia). Dit algoritme werkt als volgt:

  1. Markeer alle knopen met "niet berekend" en "niet onderzocht"
  2. Voeg de herkomstknoop toe aan de lijst te onderzoeken knopen met kosten 0
  3. Zolang er nog te onderzoeken knopen zijn en de bestemmingsknoop is nog niet onderzocht, selecteer de goedkoopste nog te onderzoeken knoop.
  4. Voor alle knopen die met één arc te bereiken zijn van de geselecteerde knoop en nog niet zijn onderzocht:
  5. Als de knoop gemarkeerd is met "niet berekend", noteer dan de kosten van de geselecteerde knoop + de kosten van de arc als de kosten bij deze knoop. Noteer ook dat de geselecteerde knoop de "vorige knoop" is in de goedkoopste route naar deze knoop.
  6. Als de knoop gemarkeerd is met "wel berekend", vergelijk dan de kosten van de geselecteerde knoop + de kosten van de arc met de huidige kosten van deze knoop en noteer het minimum. Als de route via de geselecteerde knoop de laagste kosten heeft, noteer dan ook dat de geselecteerde knoop als de "vorige knoop" is in de goedkoopste route.
  7. Markeer de knoop als berekend en voeg deze toe aan de te onderzoeken knopen en ga door met de volgende te onderzoeken knoop.

Als de bestemmingsknoop is onderzocht, dan is er een toegelaten route voor deze reis. Deze kan worden teruggevonden door vanaf de bestemmingsknoop de "vorige knoop" in de goedkoopste route te volgen totdat de herkomstknoop is bereikt.

Binnen de scenario parameters is het mogelijk om te kiezen tussen twee verschillende routeringen:

  • Shortest: het kortste pad van de herkomstknoop naar de bestemmingsknoop.
  • Shortest via reference points: het kortste pad van de herkomstknoop naar de bestemmingsknoop, via alle referentiepunten van de reis (in tijdsvolgorde).