Remember that before calling the Dijkstra algorithm, the starting/ending locations which are on links need to be pushed forward/backward to the corresponding nodes. For us, links are always uni-directional, so that the answer to this is unique. This can look as follows:
/home/nagel/src/book/router/book/RouteWorld::FindPath
Note that this calls Dijkstra. The code after the Dijkstra call takes the Dijkstra algorithm result and copies it into Plan. Plan.SetNNodes sets the number of nodes the route traverses from the start link to the destination link. Plan.SetNodeTokens sets the corresponding tokens to the node IDs. An implementation for this was already given earlier (Sec. 9.5).
Dijkstra itself can look as follows. The precise meaning of nodeList will be described afterwards; essentially, it is a container that contains all ``pending'' nodes. In Sec. 11.2 this corresponds to the set of all nodes where isDone is false but arrTime is no longer infinity.
/home/nagel/src/book/router/book/RouteWorld::Dijkstra
The implementation for NodeList is again a multimap; the functioning of this was already explained in the context of generating a random sequence of links, and in the context of the vehicle wait queue. For the wait queue, the functionality is exactly the same has here: We need to maintain a set of (key,pointer)-pairs such that it is possible to retrieve the pointer which belongs to (one of) the smallest key(s).
One issue here is that, if a better ArrTime for a node is found, it should be moved within the priority queue. This would necessitate to find that element within the queue. Another option is to leave both entries in the queue, but add the IsDone flag to nodes. If a node with IsDone is encountered, it is removed from the queue but ignored otherwise.
The expand() method is still missing. Here is a suggestion:
/home/nagel/src/book/router/book/Node::expand
tTime( . ) is a method of the Link class which returns the link travel time on that link as a function of the entering time, in the code given by now. As discussed in Sec. 11.3, at this point this should return the length of the link (in meters) divided by 7.5.