[Boost-bugs] [Boost C++ Libraries] #7387: marginal improvements to dijkstra_shortest_paths

Subject: [Boost-bugs] [Boost C++ Libraries] #7387: marginal improvements to dijkstra_shortest_paths
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-09-18 12:26:57

#7387: marginal improvements to dijkstra_shortest_paths
-------------------------------------------------+--------------------------
 Reporter:  Alex Hagen-Zanker <ahh34@…>          |       Owner:  jewillco    
     Type:  Patches                              |      Status:  new         
Milestone:  To Be Determined                     |   Component:  graph       
  Version:  Boost 1.52.0                         |    Severity:  Optimization
 Keywords:  dijkstra                             |  
-------------------------------------------------+--------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/7387>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.