Fastest Path

The typical method to obtain routes is to calculate fastest paths. This is achieved via a standard shortest path algorithm by using link travel time as link cost. These algorithms typically go from node to node, which means that we have to translate our starting and ending locations to the corresponding nodes. Such an algorithm (Dijkstra algorithm, see e.g. ()) then can proceed as follows:

• Set arrTime at all nodes to infinity. Set isDone of all nodes to false.

• Take the starting node from the trip. Make it the current node. Set its arrTime to the trip starting time.

• ``Node expansion:'' Set isDone of the current node to true. Go through all outgoing links from the current node. For each such link, calculate arrival time at toNode as
  
  $${\tt tmpArrivalTime = now + outLinkTravelTime \ ,}$$
  
  
  where now is the arrTime at the current node.

  If tmpArrivalTime is smaller than toNode's current arrTime, then a faster path to that node just has been found. In that case,

  • Set toNode's arrTime time to tmpArrivalTime.

  • Set a pointer at toNode pointing back to the current node.

• Out of all nodes where isDone is false, take the one with the minimum arrTime. Do ``node expansion'' with this node.

• Etc.

One can stop when the destination node is about to be expanded. Note that one cannot stop when the end node is touched for the first time (i.e. when its time is set from infinity to some finite value) since some better time can be found later. The full path can now be found by taking the end node, and following the pointers back to the start node.