<small id='cRJ5B'></small><noframes id='cRJ5B'>

  • <i id='cRJ5B'><tr id='cRJ5B'><dt id='cRJ5B'><q id='cRJ5B'><span id='cRJ5B'><b id='cRJ5B'><form id='cRJ5B'><ins id='cRJ5B'></ins><ul id='cRJ5B'></ul><sub id='cRJ5B'></sub></form><legend id='cRJ5B'></legend><bdo id='cRJ5B'><pre id='cRJ5B'><center id='cRJ5B'></center></pre></bdo></b><th id='cRJ5B'></th></span></q></dt></tr></i><div id='cRJ5B'><tfoot id='cRJ5B'></tfoot><dl id='cRJ5B'><fieldset id='cRJ5B'></fieldset></dl></div>

      <legend id='cRJ5B'><style id='cRJ5B'><dir id='cRJ5B'><q id='cRJ5B'></q></dir></style></legend>
      <tfoot id='cRJ5B'></tfoot>
        <bdo id='cRJ5B'></bdo><ul id='cRJ5B'></ul>
      1. 提升图中 VertexList = ListS 的 Dijkstra 最短路径

        时间:2023-06-29

            <small id='wMr6r'></small><noframes id='wMr6r'>

            <i id='wMr6r'><tr id='wMr6r'><dt id='wMr6r'><q id='wMr6r'><span id='wMr6r'><b id='wMr6r'><form id='wMr6r'><ins id='wMr6r'></ins><ul id='wMr6r'></ul><sub id='wMr6r'></sub></form><legend id='wMr6r'></legend><bdo id='wMr6r'><pre id='wMr6r'><center id='wMr6r'></center></pre></bdo></b><th id='wMr6r'></th></span></q></dt></tr></i><div id='wMr6r'><tfoot id='wMr6r'></tfoot><dl id='wMr6r'><fieldset id='wMr6r'></fieldset></dl></div>

            • <tfoot id='wMr6r'></tfoot>
                <tbody id='wMr6r'></tbody>
                • <bdo id='wMr6r'></bdo><ul id='wMr6r'></ul>
                • <legend id='wMr6r'><style id='wMr6r'><dir id='wMr6r'><q id='wMr6r'></q></dir></style></legend>
                  本文介绍了提升图中 VertexList = ListS 的 Dijkstra 最短路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着跟版网的小编来一起学习吧!

                  问题描述

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

                  I am quite new to Boost graph. I am trying to adapt an example for finding Dijkstra Shortest Path algorithm which used VertexList = vecS. I changed the vertex container to ListS. I learned that we have to provide our own vertex_index for the algorithm to work if we use listS.

                  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 > 中的'operator=' 不匹配,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>::operator* with _Tp = void*, _Tp& = void*&) = c'

                  /spvec.cpp:62:20: error: no match for ‘operator=’ in ‘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>::operator* with _Tp = void*, _Tp& = void*&) = c’

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

                  I am sure I made a mistake in creating my own vertex index. But couldnt find out exactly whats the issue. Does anyone have some suggestions on what I am doing wrong..

                  推荐答案

                  BGL 实际上有一个使用 dijkstra_shortest_paths 和 listS/listS 的例子,但它没有从 HTML 文档中链接到:http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

                  BGL actually has an example of using dijkstra_shortest_paths with listS/listS, but it's not linked to from the HTML documentation: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

                  错误消息试图告诉您什么(error: no match for 'operator=' in 'index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...) 是 vertex_index_t 属性没有每个顶点的存储,这是 adj_list_vertex_property_map 需要的.要解决此问题,您可以更改 Graph typedef 以包含 vertex_index_t 属性的每个顶点存储或使用外部"属性映射例如associative_property_map.

                  What the error message is trying to tell you (error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...) is that there is no per-vertex storage for the vertex_index_t property, which is what adj_list_vertex_property_map needs. To fix the problem you can either change your Graph typedef to include per-vertex storage for the vertex_index_t property or use an "external" property map such as associative_property_map.

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

                  The dijkstra-example-listS.cpp example uses the approach of changing the graph typedef. To use this approach in your code, you could define:

                  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;
                  

                  这篇关于提升图中 VertexList = ListS 的 Dijkstra 最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!

                  上一篇:迭代 DFS 与递归 DFS 以及不同的元素顺序 下一篇:图实现 C++

                  相关文章

                  <i id='MdkUa'><tr id='MdkUa'><dt id='MdkUa'><q id='MdkUa'><span id='MdkUa'><b id='MdkUa'><form id='MdkUa'><ins id='MdkUa'></ins><ul id='MdkUa'></ul><sub id='MdkUa'></sub></form><legend id='MdkUa'></legend><bdo id='MdkUa'><pre id='MdkUa'><center id='MdkUa'></center></pre></bdo></b><th id='MdkUa'></th></span></q></dt></tr></i><div id='MdkUa'><tfoot id='MdkUa'></tfoot><dl id='MdkUa'><fieldset id='MdkUa'></fieldset></dl></div>

                  1. <tfoot id='MdkUa'></tfoot>

                  2. <legend id='MdkUa'><style id='MdkUa'><dir id='MdkUa'><q id='MdkUa'></q></dir></style></legend>

                    <small id='MdkUa'></small><noframes id='MdkUa'>

                        <bdo id='MdkUa'></bdo><ul id='MdkUa'></ul>