Boost logo

Boost Users :

From: liu jianfei (flair.liu_at_[hidden])
Date: 2005-11-30 18:43:48


Hi, all

    Recently, I faced a big problem when I'm using the boost function
of shorthest path computing including dijkstra_shortest_paths and
johnson_all_pairs_shortest_paths. My projectet was that I extracted
all the surface voxels of a volume as the vertexs of the graph, and
26-connection between them as a edge. Hence, I got a large sparse
graph which composed of 12768 vertexs and around 86000 edges. In the
next stage, I implemented the dijkstra_shortest_paths computation for
each vertex. However, it succeded in some points and failed in other
points. If I changed the weight of each edge into 1, all points
worked. If I used other weights for different edges, then problem
poped up. Also, some points worked for this special weight, and failed
for others. I think the shortest path algorithm should be unrelated
with the weight assignment. Initially, I think something was wrong in
my graph buliding. But when I wrote the shorthest path algorithm by
myself and all points worked, I felt there may be a bug in
dijkstra_shortest_paths class. If someone else faces the same problem,
feel free to tell me. If not, I'm willing to paste my graph code in
spite of its complexity. Thanks

     Regards!


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net