在boost的dijkstra_shortest_paths中检查负边缘权重

Question

我正在使用boost图库来调用dijkstra_shortest_paths.但是,我有一些特殊的设置,因为weight_map它实际上是一个仿函数.因此,每当boost库需要边缘的权重时,我的函子被调用,进行复杂的计算并将结果返回到提升.

不幸的是,在dijkstra_shortest_paths.hppstruct dijkstra_bfs_visitor的方法examine_edge中get调用了weightmap,只检查返回的值是否为负数.我完全清楚我不能使用负值的Dijkstra算法,我确信我的仿函数只返回正值.但是,此检查会导致我的仿函数为每个边缘调用两次.因为它执行一个复杂的计算,我想避免执行两次(结果不会在调用之间改变..每个边缘在dijkstra_shortest_paths运行期间获得相同的等待).

到目前为止,我手动检查传递给仿函数的边缘,如果重复调用,我将返回上一个记忆结果.这显然是一种解决方法而不是解决方案.

我试图通过我自己的覆盖覆盖的访问者examine_edge,然而,dijkstra_bfs_visitor仍然应用了由boost定义的原始方法.

有谁知道是否有更好的方法来处理这种情况,并以某种方式避免否定边缘权重检查？

Answer 1

你是对的，甚至向你自己的访客提供消极测试。

  void examine_edge(Edge e, Graph& g) {
    if (m_compare(get(m_weight, e), m_zero))
        boost::throw_exception(negative_edge());
    m_vis.examine_edge(e, g);
  } 

但无论如何，weight_map 应该被多次调用（参见 boost doc）：

 for each vertex v in Adj[u]
  if (w(u,v) + d[u] < d[v])
    d[v] := w(u,v) + d[u]

只需使用预先计算的权重图调用 djikstra，无论如何都必须计算每个边的权重。