Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths

Subject: Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths
From: Stephen Woodbridge (woodbri_at_[hidden])
Date: 2011-06-29 20:09:31

On 6/29/2011 6:07 PM, Stephen Woodbridge wrote:
> Hi all,
>
> I am C programmer floundering in a C++ world!
> I have the function that I call from C that builds a graph, runs
> dijkstra_shortest_paths(), then extracts the results and passes them
> back to a C array of structs. Code is in pastebin:
>
> http://pastebin.com/xi7vLpTx
>
> This seems to work and everything looks ok, EXCEPT the edge ids are not
> correct. I suspect this is because I'm not doing something correctly and
> I have been messing with this for a couple weeks without success, so I
> think its time to ask for help.
>
> So in the function:
>
> graph_add_edge(G &graph, int id, int source, int target, float8 cost)
>
> id is the edge id
> source is the node id at the start of the edge
> target is the node_id at the end of the edge
> cost is the cost to traverse the edge from source to target
>
> I would really appreciate it if someone could look at this and point out
> what I might be doing wrong.

OK, a little more information that might help:

1. I'm using Boost 1.34 on Linux Debian Lenny which is pretty old but I 
can't upgrade this system yet. I could try this on another system if you 
think this is the problem.

2. boost_dijkstra_nodes() is always called with directed=false and 
has_reverse_cost=false but the graph is always built as directed with 
both the u-v and v-u edges added with the same cost.

3. I thinking that may be the problem is that I'm associating the edge 
is with a vertex id, but any given vertex can have multiple edges 
associated with it and may be I should be using a PropertyTag on the 
edge instead of what I am doing now.

Thanks again for any input,
   -Steve