on Thu Nov 03 2011, Stephen Woodbridge wrote:

Hi all,

I need to solve Dijkstra shortest path with turn restrictions. I am wondering if anyone has an example of how to implement this?

I'm thinking that this can be done something like this:

1. a restriction(s) could be represented as: at a given node X if my ancestry is some list of of nodes, then restrict going forward to a node or list of nodes.

2. any given node can optionally have a list of restrictions attached to it

3. a visitor function would then get the list of restrictions for the visited node and compare ancestor list of each restriction to the current path ancestry and then filter forward nodes if there is an ancestry match(s).

Does this sound like a reasonable approach?

I don't think that's enough. Dijkstra depends on the idea that any path that reaches a node X can be joined to any path that proceeds from node X. IMO your underlying graph G=(V,E) isn't the appropriate one to which to apply Dijkstra. IMO you need to produce a different graph G' having a distinct vertex descriptor for each distinct pair (v,S) where v ∋ V and S is a set of available outgoing edges in of v. -- Dave Abrahams BoostPro Computing http://www.boostpro.com