Negative edge weight check in boost dijkstra_shortest_paths

Question

I use the accelerator library to call dijkstra_shortest_paths . However, I have something special, since weight_map is actually a functor. Therefore, every time the acceleration library requires the weight of an edge, my functor is called, does a complicated calculation, and returns the result for a boost.

Unfortunately, in dijkstra_shortest_paths.hpp the struct dijkstra_bfs_visitor examine_edge has a get call to the weight map, only to check if the return value is negative. I fully understand that I cannot use Dijkstra's algorithm with negative values, and I am sure that my functor returns positive values. However, this check forces my functor to be called twice for each edge. Since it performs complex calculations, I would like not to do it twice (the results do not change between calls .. each edge gets the same wait while running dijkstra_shortest_paths ).

So far, I have manually checked the edge passed to the functor, and in case of duplicate call, I return the previous stored result. This is clearly a more workaround than a solution.

I tried to pass on my visitor who overwrites examine_edge , however the original method defined by boost dijkstra_bfs_visitor still applies.

Does anyone know if there is a better way to handle this situation and somehow avoid checking the negative edge weight?

Answer 1

You are right, even by supplying you with your own visitor, a negative test 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 in any case, weight_map is supposed to be called multiple (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 pre-computed weight map, each edge weight must be calculated anyway.

Answer 2

I suggest you use lazy calculations to ensure that every expensive calculation is done no more than once. The easiest way to implement this is to give you the Edge a getWeight() class, a lazy getter, I'm not familiar with the library you are using, so I'm not sure how you integrate this with the functor.