带平行边的Boost图中，如何获取Dijkstra最短路径的边信息？

云上老周

2026-6-12

解决带平行边图中Dijkstra路径边的提取问题

核心问题在于仅靠前驱节点映射无法确定平行边中被Dijkstra选中的那条，最简便的方案是直接让Dijkstra记录前驱边而非前驱节点，具体实现如下：

步骤1：定义前驱边存储容器

代替原来的顶点类型前驱映射，使用边类型的容器来存储每个节点的前驱边：

// 假设fg是你的图对象，vertex_t是顶点类型，edge_t是边描述符类型
std::vector<edge_t> pred_edges(num_vertices(fg));

步骤2：调用Dijkstra时指定前驱边映射

调用dijkstra_shortest_paths时，将predecessor_map参数设置为该边容器的迭代器适配对象：

dijkstra_shortest_paths(
    fg,
    source_vertex, // 你的源顶点
    predecessor_map(boost::make_iterator_property_map(
        pred_edges.begin(),
        get(boost::vertex_index, fg)
    )).distance_map(...) // 补充你需要的距离映射等其他参数
);

步骤3：提取路径边

遍历路径时，直接从pred_edges中获取Dijkstra选中的边，无需再通过节点查找：

for (auto v : boost::make_iterator_range(vertices(fg))) {
    typedef std::vector<edge_t> PathType;
    PathType path;
    vertex_t vv = v;
    edge_t current_edge = pred_edges[vv];
    
    // 遍历直到回到源节点（源节点的前驱边为无效值）
    while (boost::edge_is_valid(current_edge, fg)) {
        path.push_back(current_edge);
        // 移动到前驱节点，获取下一条前驱边
        vv = boost::source(current_edge, fg);
        current_edge = pred_edges[vv];
    }
    
    // 若需要正序路径，可反转结果
    std::reverse(path.begin(), path.end());
}