c++ - boost 的 dijkstra_shortest_paths 中的负边权重检查

Question

我正在使用 boost 图形库调用 dijkstra_shortest_paths。但是，我有一些特殊的设置，因为 weight_map 实际上是一个仿函数。因此，每当 boost 库需要边的权重时，我的仿函数就会被调用，进行复杂的计算并将结果返回给 boost。

不幸的是，在 dijkstra_shortest_paths.hpp 结构 dijkstra_bfs_visitor 的方法 examine_edge 中有一个 get 调用weightmap，只检查返回值是否为负数。我完全清楚我不能将 Dijkstra 算法与负值一起使用，并且我确信我的仿函数只返回正值。但是，此检查会导致我的仿函数在每条边上被调用两次。因为它执行复杂的计算，所以我想避免执行两次(结果在调用之间不会改变.. 在 dijkstra_shortest_paths 运行期间，每个边都得到相同的等待)。

到目前为止，我正在手动检查传递给仿函数的边缘，如果重复调用，我将返回之前记住的结果。这显然更像是一种解决方法，而不是解决方案。

我试图传递覆盖examine_edge的我自己的访问者，但是，仍然应用了boost的dijkstra_bfs_visitor定义的原始方法。

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

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，无论如何都必须计算每条边的权重。