时间戳

首页 > 解决方案 > 有没有办法在 boost dijkstra 算法期间减轻 IndexInHeapMap 初始化？

c++ - 有没有办法在 boost dijkstra 算法期间减轻 IndexInHeapMap 初始化？

问题描述

上下文：我的代码使用 boost dijkstra 算法在 13.4M 顶点/33M 边图上执行寻路。在进行分析时，我注意到 60% 的 dijkstra 调用由初始化 a IndexInHeapMapduring的调用支配dijkstra_shortest_paths_no_color_map_no_init。我怀疑由于图形大小需要很长时间

有没有办法避免/减少这种初始化成本？

也许最糟糕的是，我们的 dijkstra 调用是有上限的，并且与图大小相比并没有执行很多迭代

我查看了boost source，发现在某个时候，宏允许使用替代队列 ( BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP)。但是我找不到关于它的文档，而且这部分似乎在更新的版本中被删除了（我们使用 v1.62）

我对提升 dijkstra 的确切呼吁是

boost::dijkstra_shortest_paths_no_color_map_no_init(
      graph,
      sourceVertex,
      &(predecessors[0]),
      &(distances[0]),
      weights,
      vertexIndex,
      std::less<uint32_t>(),
      boost::closed_plus<uint32_t>(),
      infinity,
      zero,
      visitor
);

然后在boost代码里面，这个区域变得很长

    typedef
      detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t>
      IndexInHeapMapHelper;
    typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
    typedef
      d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare>
      VertexQueue;
  
    boost::scoped_array<std::size_t> index_in_heap_map_holder;
    IndexInHeapMap index_in_heap =
      IndexInHeapMapHelper::build(graph, index_map, // <--- Take 60% of scope runtime
                                  index_in_heap_map_holder);  
    VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);

标签： c++boostdijkstrapath-findingboost-graph

解决方案

推荐阅读