Negative edge weight check in boost's dijkstra_shortest_paths

I am using the boost graph library to make a call to dijkstra_shortest_paths. However, I have something special setup in that the weight_map is actually a functor. Hence, everytime the boost library requires the weight of an edge, my functor is called, makes a complicated computation and delivers the result back to boost.

Unfortunately, in dijkstra_shortest_paths.hpp the struct dijkstra_bfs_visitor's method examine_edge has a get call to the weightmap, only to check if the returned value is negative. I am fully aware that I cannot use Dijkstra's algorithm with negative values and I am certain that my functor only returns positive values. However, this check causes my functor to be called twice for each edge. As it performs a complicated computation I'd like to avoid performing it twice (the results don't change between calls.. each edge gets the same wait during a dijkstra_shortest_paths run).

So far, I am manually checking the edge passed to the functor and in case of the duplicate call I am returning the previous remembered result. This clearly is more of a workaround than a solution.

I tried to pass my own visitor that overwrites examine_edge, however, the original method defined by boost's dijkstra_bfs_visitor is still applied.

Does 开发者_运维百科anyone know if there is a better way to handle this situation and somehow avoid the negate edge weight check?

You are right, even supplying you own visitor the test of negativity will be performed.

  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);
  } 

But anyway the weight_map is supposed to be called multiple time (see boost doc):

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

Just call djikstra with a precomputed weight map, every edge weight will have to be computed anyway.

I suggest you use lazy computation to ensure that each expensive computation is carried out at most once. The most straightforward way to implement this would be give your Edge class a getWeight() lazy getter, I'm not familiar with the library you're using so I'm not sure how you'd integrate that with the functor.