allow repeating nodes on shortest path computation

[carocad]

Currently we use the classical DIjkstra algorithm for finding the shortest path between two nodes of a graph.

This approach works well as long as complicated turn restrictions are not allowed. In OpenTripPlanner they use something called the "Governance model" which apparently allows them to settle nodes more than once.

See last paragraph https://github.com/opentripplanner/OpenTripPlanner/wiki/GraphStructure

Turn restrictions are now handled by annotating edges to explicitly allow or disallow turns onto other edges for individual modes of travel. These restrictions are applied on the fly during the search. Note that due to turn restrictions, a shortest path can pass through an intersection more than once when a shortest path loops back on itself. This special case is handled in the state dominance function that determines when two states can coexist at a vertex.

Other references:

• http://docs.pgrouting.org/2.0/en/src/trsp/doc/index.html

[carocad]

Turns out this is not a bug since the Dijkstra algorithm was never meant to contain loops