[Boost-users] The problem about shorthest path computation

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!