使用Boost Graph库Dijkstra算法找最短路径时[]运算符报错

你遇到的[]运算符未定义错误，核心原因是顶点存储类型setS导致vertex_descriptor不是整数类型，而你试图用它作为vector的下标——vector的[]只接受整数索引，自然会触发这个报错。

为什么会这样？ #

Boost Graph库中，adjacency_list的第二个模板参数决定了顶点的存储方式：

• 当使用vecS时，顶点被存在连续的vector里，vertex_descriptor就是从0开始的整数索引，能直接作为vector的下标使用。
• 但你选了setS，这种存储方式下顶点是无序集合，vertex_descriptor是类似迭代器的非整数类型，完全不符合vector下标要求。

两种解决方案 #

方案1：改用vecS作为顶点存储（推荐，性能更优）

如果你的场景不需要频繁删除顶点，优先选vecS——它不仅能解决下标问题，还能提升算法运行效率：

修改你的图类型定义：

// 把第二个参数从setS改成vecS
typedef adjacency_list<vecS, vecS, directedS, VertexIDPorperty, tEdgeProperty> tGraph;

修改后vertex_descriptor会变成整数类型，你原来的vector<tVertex> p和current = p[current]代码就能正常工作了。

方案2：使用关联容器存储前驱映射（必须保留setS时）

如果必须用setS，需要用关联容器（比如std::map）存储前驱关系，再用Boost的associative_property_map包装，让它符合Dijkstra算法要求的property map接口：

修改后的完整代码示例：

typedef property<edge_weight_t, double, property<edge_index_t, tElementIDVector>> tEdgeProperty;
typedef property<vertex_index_t, tElementID> VertexIDPorperty;
typedef adjacency_list<vecS, setS, directedS, VertexIDPorperty, tEdgeProperty> tGraph;
typedef tGraph::vertex_descriptor tVertex;
typedef tGraph::edge_descriptor tEdge;

// 用map存储前驱关系，并用associative_property_map包装
std::map<tVertex, tVertex> p_map;
boost::associative_property_map<std::map<tVertex, tVertex>> p(p_map);
vector<double> d(num_vertices(graph));

// 调用Dijkstra算法时传入包装后的前驱映射
dijkstra_shortest_paths(graph, s, 
    predecessor_map(p)
    .distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));

// 查找路径的代码可以直接用p[current]
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start) {
    pathVertices.push_front(current);
    current = p[current]; // 现在可以正常访问了
}

额外提示 #

• setS适合需要频繁删除顶点的场景，但会带来额外性能开销（关联容器访问是O(log n)，而vector是O(1)）。
• 建议在路径查找的循环中加入判断（比如检查当前顶点是否存在于前驱映射中），避免因start无法到达goal导致无限循环。

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