marginal improvements to dijkstra_shortest_paths

[Alex Hagen-Zanker <ahh34@…>]

There are a couple of details in the dijkstra_shortest_path calculation that potentially make the implementation less efficient than strictly necessary. All considered the change in performance is marginal. But the code will be more to the point and I was happy to no longer use boost::closed_plus.

1. The tree_edge member function and the gray_target member function call the relax() function. In case of undirected graphs, this function attempts to relax both the target and the source of the edge. This is right for some algorithms (e.g. Bellman-Ford) but not for others (e.g. Dijkstra Shortest Paths). It would therefore be preferred to introduce a new function relax_target(), that only relaxes the target of an edge.

2. The defaults algorithm for summing weights and distances is boost::closed_plus<T>. This implements a simple plus operation with the extension that x + inf = inf, where inf is a special value set upon initialization. Note that this is not a generic guard against overflows, but only works if one of the inputs is equal to inf. If the new relax_target() is used, then it is no longer necessary to use boost::closed_plus and simple std::plus will suffice. (*)

3. The tree_edge member function of the dijkstra_bfs_visitor is called when a new vertex is found. The distance for this vertex must always reduce. Several checks in relax() or relax_target() are therefore not necessary, and it is recommended to add a function relax_target_confident().(*)

4. If the relax_target_confident function is used, then any comparison with distance_inf values is avoided. Strictly speaking it is not longer necessary to initialize the values of the distance map, and the precise value becomes irrelevant to the algorithm.

5. The update() function for the d-ary-heap does not need the old_distance therefore the gray_target member function does not need to call it.

(*). There could possibly be one other reason to use boost::closed_plus and that is the case of edge_weights being equal to distance_inf. This could be a hackish way of excluding edges from the shortest path search and IMO does not need to be supported.

[Alex Hagen-Zanker <ahh34@…>]

minor improvements

[Luis G. Torres <lgtorres42@…>]

Is there any word on whether this will be included? This looks really useful (especially point 4, which would remove an entire argument from the dijkstra function and allows for some edge cost functions where distance_inf is hard to define).

[anonymous]

The documentation since 1.53 clarifies that edge weights are assumed to have a value smaller than distance_inf. So the possibility of edge weight == distance_inf is no longer an issue (hurray).

www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html