The documentation for 1.58.0 (http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/r_c_shortest_paths.html) correctly states that:
The implementation is a label-setting algorithm. This means that there must be one or more resources whose cumulated consumption(s) after extension is/are always at least as high as before. This is similar to the Dijkstra algorithm for the SPP without resource constraints where the distance measure must be non-negative. It is sufficient if there is one resource with a non-negative resource consumption along all arcs (for example, non-negative arc lengths or non-negative arc traversal times).
But, later on, it says:
If ref models the ResourceExtensionFunction concept, and if the type Resource_Container models the ResourceContainer concept, after the call
ref( const Graph& g, Resource_Container& new_cont, const Resource_Container& old_cont, graph_traits<Graph>::edge_descriptor ) the expression old_cont <= new_cont evaluates to true. This is because, as stated above, the implementation is a label-setting algorithm. Therefore, the Less-Than operator for ResourceContainer must compare one or more resource(s) whose resource consumption(s) along any arc is/are non-decreasing in order for the algorithm to work properly.
Now, saying that "old_cont <= new_cont" is much stricter than it should be. The correct requirement (first quote) is that there is **at least one** resource whose consumption monotonically doesn’t decrease. What "old_cont <= new_cont” requires, is that **all** resources’ consumptions are monotonically non-decreasing. These two things are equivalent iff the label only has one resource. Can someone confirm that my observation makes sense? In this case, I’ll open a ticket and submit a patch for the documentation. Can someone also confirm that this check is *not* enforced in r_c_shortest_paths.hpp? Thanks, AS