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

From: Greg Link (link_at_[hidden])
Date: 2006-02-16 13:33:12

Aaron (and the rest of the Boost-user's list) -
        I've attached a link to a .tar.gz of the source code I'm using,  
which currently requires both boost and the matpack library (for  
shepard interpolation), however, the only use of the matpack library  
is in the function "init_tsmap", where two "if(use_interpolation)"  
statements differentiate the code that needs matpack from a non- 
matpack codepath that simply instantiates the values in the tsmap to  
random values (originally put in to allow debugging the rest of the  
code separately from matpack). Hence, if you don't have matpack, you  
can just delete/ifdef out the matpack-based codepath.

        If you do have matpack, the executable " ./a.out 20 70 80 95 106"  
will read in the "input.dat" file, generate a tsmap object, then a  
graph, and attempt to find the shortest paths from the node at [20%,  
70%] to [80%, 95%], with a graph of 106x106 nodes. Many other calls  
(such as the same points at a grid size of 105) return a shortest  
path that is, in fact, shorter than the manhattan paths, but if code  
fails in one weird case, you can be sure something is wrong  
somewhere, so can't really claim it works.

        If you don't have matpack, the code initializes a tsmap with random  
values, and thus a graph with random weights, so I don't have a case  
that will cause it to fail available. I have, however, provided  
a .dot (graphviz) format file "dump-00.dot" of the entire graph, with  
each edge labeled with the appropriate weight.

        As a final statement, please forgive the quality of the source  
provided. It's still very much a work-in-progress, and as the  
specifications change hourly, so do the data formats, function  
interfaces, et cetera. Always embarrassing to have something other  
than one's best work on public display.

- Greg

To reduce message size, I've provided download links for all files,  
rather than attaching them directly.

Source: http://www.cse.psu.edu/~link/link_dijkstra.cpp.gz

Text files listing the paths: http://www.cse.psu.edu/~link/ 
path_listings.tar.gz

Graphviz-format output file (takes a lot of memory to render - over  
11 thousand edges): http://www.cse.psu.edu/~link/dump-00.dot.gz

SVG-format file demonstrating the problem in a much more useful  
visual format (viewable in any cutting-edge browser, such as Firefox,  
Nightly Safari WebKit builds, or using the Adobe SVG plugin) : http:// 
www.cse.psu.edu/~link/svg-00.svg.gz

On Feb 15, 2006, at 6:47 AM, Aaron Windsor wrote:

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>

Greg,

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

Thanks,
Aaron