gpt4 book ai didi

c++ - Dijkstra 最短路径与 VertexList = ListS in boost graph

转载 作者:可可西里 更新时间:2023-11-01 16:33:27 25 4
gpt4 key购买 nike

我对 Boost 图还很陌生。我正在尝试改编一个示例来查找使用 VertexList = vecS 的 Dijkstra 最短路径算法。我将顶点容器更改为 ListS。我了解到,如果我们使用 listS,我们必须为算法提供我们自己的 vertex_index 才能工作。

int main(int, char *[])
{
typedef float Weight;
typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
typedef boost::property<boost::vertex_index_t, int> IndexProperty;

typedef boost::adjacency_list < boost::listS, boost::listS, boost::directedS,
NameProperty, WeightProperty > Graph;

typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
typedef boost::graph_traits <Graph>::vertex_iterator Viter;

typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;

typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;

Graph g;


Vertex v0 = boost::add_vertex(std::string("v0"), g);
Vertex v1 = boost::add_vertex(std::string("v1"), g);
Vertex v2 = boost::add_vertex(std::string("v2"), g);
Vertex v3 = boost::add_vertex(std::string("v3"), g);

Weight weight0 = 5;
Weight weight1 = 3;
Weight weight2 = 2;
Weight weight3 = 4;

boost::add_edge(v0, v1, weight0, g);
boost::add_edge(v1, v3, weight1, g);
boost::add_edge(v0, v2, weight2, g);
boost::add_edge(v2, v3, weight3, g);


std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents
std::vector<Weight> distances(boost::num_vertices(g)); // To store distances

IndexMap indexMap; // = boost::get(boost::vertex_index, g);
NameMap name;
Viter i, iend;
//Create our own vertex index. This is what I changed in the original code
int c = 0;
for (boost::tie(i, iend) = vertices(g); i != iend; ++i, ++c) {
indexMap[*i] = c; // **Error points to this line**
name[*i] = 'A' + c;
}
PredecessorMap predecessorMap(&predecessors[0], indexMap);
DistanceMap distanceMap(&distances[0], indexMap);
boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap));


// Extract a shortest path
std::cout << std::endl;
typedef std::vector<Graph::edge_descriptor> PathType;
PathType path;
Vertex v = v3;
for(Vertex u = predecessorMap[v];
u != v; // Keep tracking the path until we get to the source
v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor, and the predecessor to one level up
{
std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g);
Graph::edge_descriptor edge = edgePair.first;
path.push_back( edge );
}

// Write shortest path
std::cout << "Shortest path from v0 to v3:" << std::endl;
float totalDistance = 0;
for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator != path.rend(); ++pathIterator)
{
std::cout << name[boost::source(*pathIterator, g)] << " -> " << name[boost::target(*pathIterator, g)]
<< " = " << boost::get( boost::edge_weight, g, *pathIterator ) << std::endl;

}

std::cout << std::endl;

std::cout << "Distance: " << distanceMap[v3] << std::endl;

return EXIT_SUCCESS;
}

我收到以下错误:

/spvec.cpp:62:20: 错误:在 'index.boost::adj_list_vertex_property_map::operator[] [with Graph = boost::adjacency_list >, boost::property >, ValueType = boost::detail::error_property_not_found, Reference = boost::detail::error_property_not_found&, Tag = boost::vertex_index_t, boost::adj_list_vertex_property_map::key_type = void*](i.std::_List_iterator<_Tp>::运算符* with _Tp = void*, _Tp& = void*&) = c'

我确定我在创建自己的顶点索引时犯了一个错误。但无法找出到底是什么问题。有没有人对我做错了什么有一些建议..

最佳答案

BGL其实有一个使用dijkstra_shortest_paths的例子使用 listS/listS,但未链接到 HTML 文档:http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

错误消息试图告诉您 ( error: no match for ‘operator=’ in ‘index.boost::<strong>adj_list_vertex_property_map</strong>...ValueType = boost::detail::<strong>error_property_not_found</strong>... ) 没有针对 vertex_index_t 的逐顶点存储属性(property),这是什么adj_list_vertex_property_map需要。要解决此问题,您可以更改 Graph typedef包括 vertex_index_t 的每个顶点存储属性或使用“外部”属性映射,例如 associative_property_map .

dijkstra-example-listS.cpp示例使用更改图形的方法 typedef .要在您的代码中使用这种方法,您可以定义:

typedef boost::adjacency_list <boost::listS, boost::listS, boost::directedS,
boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int> >,
boost::property<boost::edge_weight_t, Weight> > Graph;

关于c++ - Dijkstra 最短路径与 VertexList = ListS in boost graph,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7156880/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com