On 2/14/06, Greg Link
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