Re: [Boost-users] [Graph] New user finding dijkstra's isn't returning shortest paths

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-02-15 06:47:51

On 2/14/06, Greg Link <link_at_[hidden]> wrote:
> In my first use of the boost library, I'm using the BGL's
> dijkstra_shortest_paths algorithm to try and (obviously) find the
> shortest path between two points. I am then iterating along the
> shortest path to a given node to find the total path weight along
> that path. I compare this value to the path weight along a manhattan
> path, and find that the manhattan path is shorter. Rather than claim
> this is a problem with boost (yet), I'm at first believing it's my
> interpretation of the library. If I've piqued your interest, feel
> encouraged to read on.

<snip>

> I've checked my corner cases, and the paths are only being summed
> along relevant edges (no off-by-one errors that I can see, at least).
> If anyone has any ideas on how I might best debug/change my code, or
> a means by which I can perform some other test, I'd love to hear it.
> If anyone needs any more information, the code is by no means
> confidential (though a bit messy) and I've got both .dot (graphviz)
> format and an svg representation of the graph available. My
> development platform is currently Mac OS X 10.4.4 PPC using Xcode, if
> it matters to anyone.
>
> Thanks, and I hope you don't mind the rather lengthy post!
> - Greg Link

Greg,

Could you zip up your code and the .dot input file and post them, if
the file isn't too big?

Thanks,
Aaron