代码之家  ›  专栏  ›  技术社区  ›  Gnosophilon

boost::dijkstra_shortest_path是否覆盖内部图权重?

  •  2
  • Gnosophilon  · 技术社区  · 12 年前

    我正在使用Boost图库来存储一个无向图 double 边缘权重和 双重的 顶点权重。在我的代码中的几个地方,我需要应用Dijkstra的算法来搜索最短路径。这非常有效,直到我决定用自己的权重临时覆盖存储的边权重(只是暂时的,图形权重不会被修改)。我的代码基本上是这样的:

      // Initial typedefs
    
      typedef boost::property<boost::edge_weight_t, double> edge_weight_t;
      typedef boost::property<boost::vertex_discover_time_t, double> vertex_weight_t;
      typedef boost::adjacency_list<boost::vecS,
                                    boost::vecS,
                                    boost::undirectedS,
                                    vertex_weight_t,
                                    edge_weight_t> graph_t;
    
     // In a function, where graph is a const reference of type graph_t
    
     std::vector<double> pathLengths( boost::num_vertices( graph ) );
    
     boost::property_map<graph_t, boost::edge_weight_t>::type weightMap;
     boost::graph_traits<graph_t>::edge_iterator e_it, e_it_end;
     for( boost::tie( e_it, e_it_end ) = boost::edges( graph );
          e_it != e_it_end;
          ++e_it )
     {
       weightMap[ *e_it ] = 1.0;
     }
    
     boost::dijkstra_shortest_paths( graph,
                                     boost::vertex( vertex, graph ),
                                     boost::distance_map( &pathLengths[0] ).weight_map( weightMap ) );
    

    虽然 graph 是一个 常量引用 在上面的代码中,图的边权重为 已更改 之后我做错了什么?或者更具体地说,如何临时覆盖加权图中的边权重?

    显然,我可以简单地存储当前的边权重,用我的权重替换它们,然后再更改回来。然而,我确信 我有过错,我不想忽视这个问题。

    1 回复  |  直到 12 年前
        1
  •  4
  •   user1299170    12 年前

    我相信,我也遇到了同样的问题——我想暂时(对于搜索算法的特定运行)修改边权重,而不永久改变图本身。经过一番搜索,我发现了这个,它允许您注册一个用于生成权重的函子。这用作weight_map参数:

    http://www.boost.org/doc/libs/1_51_0/boost/property_map/function_property_map.hpp