id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
7387	marginal improvements to dijkstra_shortest_paths	Alex Hagen-Zanker <ahh34@…>	Jeremiah Willcock	"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. "	Patches	new	To Be Determined	graph	Boost 1.52.0	Optimization		dijkstra