使用自定义顶点索引的Boost Graph调用Dijkstra算法报错求助

当使用boost::listS作为顶点容器时，Boost Graph不会自动提供vertex_index属性（该属性仅在vecS容器中默认存在，因为vecS的顶点描述符本身就是整数索引）。直接使用get(&Vertex::id, g)作为索引映射时，由于自定义ID并非连续的0-base整数（比如你的ID是1、2、5、6、7），而存储前驱/距离的vector大小为num_vertices(g)=5，算法尝试访问d[5]或d[7]时会触发越界，同时iterator_property_map无法适配非连续索引与vector迭代器的匹配。

方案一：手动维护连续顶点索引映射 #

给每个顶点描述符分配连续的0-base整数索引，用std::map维护映射关系，再转换为Boost的property map供Dijkstra使用：

// 创建顶点描述符到连续索引的映射
std::map<vertex_descriptor, int> vertex_index_map;
int idx = 0;
for (auto v : boost::make_iterator_range(vertices(g))) {
    vertex_index_map[v] = idx++;
}
// 转换为Boost可识别的associative property map
auto index_map = boost::make_associative_property_map(vertex_index_map);

// 初始化前驱和距离容器，大小与顶点数量一致
std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));

vertex_descriptor source_idx = vertex(1, g);

// 调用Dijkstra算法，传入自定义索引映射
dijkstra_shortest_paths(g, source_idx,
    boost::predecessor_map(boost::make_iterator_property_map(p.begin(), index_map))
    .distance_map(boost::make_iterator_property_map(d.begin(), index_map)));

方案二：使用关联容器存储结果 #

无需维护连续索引，直接用std::map以自定义顶点ID为键存储前驱和距离，避免vector越界问题：

// 创建顶点ID的property map
auto id_map = boost::make_function_property_map<vertex_descriptor>(
    [&g](vertex_descriptor v) { return g[v].id; }
);

// 用map存储前驱和距离，键为自定义顶点ID
std::map<int, vertex_descriptor> predecessor_map;
std::map<int, int> distance_map;

// 转换为Boost可识别的associative property map
auto p_map = boost::make_associative_property_map(predecessor_map);
auto d_map = boost::make_associative_property_map(distance_map);

vertex_descriptor source_idx = vertex(1, g);

// 调用Dijkstra算法，显式指定边权重map避免编译歧义
dijkstra_shortest_paths(g, source_idx,
    boost::predecessor_map(p_map)
    .distance_map(d_map)
    .weight_map(get(boost::edge_weight, g)));

• 方案一适合需要高效结果访问的场景，vector的访问速度优于map，连续索引也符合Boost算法的常规使用习惯。
• 方案二更灵活，无需额外维护连续索引，直接使用自定义稳定ID作为键，适合ID范围较大或不连续的场景。

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