c++ 使用Dijkstra查找boost图中的最短路径

u1ehiz5o 于 2023-06-25 发布在其他

关注(0)|答案(2)|浏览(233)

我是boost图形库的新手，我试图使用boost图形库在Graph中找到从一个顶点到另一个顶点的最短路径。我找到了一些关于如何使用前任Map的说明，但它对我不起作用。当我尝试调用p[some_vertex]时，我得到一个错误，说[]运算符没有定义。有人能告诉我为什么，我做错了什么吗？

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;
vector<tVertex> p(num_vertices(graph));
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s,
    predecessor_map(&p[0]).
    distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
    pathVertices.push_front(current);
    current = p[current];     //this is where the error occures
}

c++

来源：https://stackoverflow.com/questions/50351107/finding-the-shortest-path-in-a-boost-graph-using-dijkstra

2条答案

按热度按时间

ppcbkaq51#

cppreference：
std：：vector：：operator[]

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

接受**size_t**指定向量元素的位置。
但是在代码中，current的类型是tVertex。
如果你想使用operator[]和tVertex参数，你应该覆盖它。

赞(0）回复(0）举报 2023-06-25

weylhg0b2#

我不能让你的想法工作，现在不得不做一些其他的改变，这就是为什么我改变了我的前任Map现在：

typedef boost::property_map < tGraph, boost::vertex_index_t >::type IndexMap;
typedef boost::iterator_property_map < tVertex*, IndexMap, tVertex, tVertex& > PredecessorMap;
tVertex s = start;
IndexMap indexMap = get(vertex_index, graph);
vector<tVertex> p(num_vertices(graph));
PredecessorMap predecessorMap(&p[0], indexMap);
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s, predecessor_map(predecessorMap).distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
    pathVertices.push_front(current);
    current = predecessorMap[current];
}

而且现在还能用：）

展开查看全部

赞(0）回复(0）举报 2023-06-25

我来回答

c++ 使用Dijkstra查找boost图中的最短路径

2条答案

相关问题

热门标签

最新问答