使用Boost Dijkstra算法无法提取路径（检测到循环）的问题排查

你遇到的问题核心是调用Boost的dijkstra_shortest_paths时，把源节点（起点）和目标节点搞反了，导致算法计算的路径方向完全错误，最终出现自循环的情况。

具体分析： #

Boost的dijkstra_shortest_paths函数的第二个参数是算法的起始节点，也就是你要从哪个节点出发计算最短路径。但你的代码里写的是：

dijkstra_shortest_paths(g->graph, goal, ...);

这相当于让算法计算从goal到所有其他节点的最短路径，而不是你需要的从start到goal的路径。

当goal作为源节点时：

• 它的前驱节点会被设置为自身（因为源节点没有前驱）
• 算法只会填充从goal可达节点的前驱信息，而你需要的是从start出发到goal的前驱链，这完全是反向的
• 所以当你尝试从goal往start回溯路径时，第一步就遇到current == predecessors[current]，触发循环检测

修正方案： #

把dijkstra_shortest_paths的第二个参数改成start，同时保持其他参数不变：

dijkstra_shortest_paths(g->graph, start, boost::weight_map(boost::get(&Edge::weight, g->graph))
 .distance_map(boost::make_iterator_property_map(distances.begin(), idmap))
 .predecessor_map(boost::make_iterator_property_map(predecessors.begin(), idmap)) );

另外还有一个小细节需要注意：你的distances数组用了std::vector<int>，但你的边权是浮点类型（计算式里有1.0和平方项），这会导致距离值被截断，可能影响路径计算结果。建议改成std::vector<double>：

std::vector<double> distances(boost::num_vertices(g->graph));

验证修正逻辑： #

修正后，算法会计算从start到所有节点的最短路径，predecessors数组会记录每个节点在最短路径上的前驱节点。这时候你从goal开始回溯到start，就能得到正确的路径链，和你用Python版本得到的结果一致。

内容的提问来源于stack exchange，提问作者fferri