Hi Harry, hmmm. Yeah, I can see some utility there. I presume it redoes the summation of the distances but checks each sum for overflow? I wonder if it's completely reliable when negative distances are involved. I mean, I wonder if overflow somewhere during the search could cause it to give a suboptimal answer that contains no overflow, meaning that a reliable check would require basically redoing the algorithm with checked arithmetic. In that case, the user may as well just use the checked version first -- no need to run the unchecked algorithm. But then, this is a universal issue of numerics, it's not specific to SSSP. If the user is not sure that their input satisfies the requirements, I'm not sure calling a second function to validate the answer given for their possibly-invalid input makes sense. They're better off choosing to use a safe, checked numeric type from the start that will throw an exception on arithmetic error. Curious to hear what others think. Cheers. Jeremy On Fri, 17 Oct 2025 at 17:29, HARRY QIAN via Boost <boost@lists.boost.org> wrote:
Hi all,
The `dijkstra_shortest_paths()` function has a `distance_inf` parameter, which is supposed to be the greatest value of any `D` object, where `D` is the value type of the DistanceMap.
When each edge in an input graph has weight less than `distance_inf` but the shortest path between two nodes has total distance more than `distance_inf`, `dijkstra_shortest_paths()` return the shortest path between these nodes as `distance_inf`.
I could see that requiring the user to pre-validate the graph and make sure no distances surpass `distance_inf` is helpful for keeping the code concise. But in LEDA, another C++ graph library, I found a function `CHECK_SP()` which checks if the result of a single source shortest path computation is correct (including if any overflow occurred due to setting `distance_inf` too small). To my knowledge such a result-checking function doesn't exist in the Boost Graph Library.
Would implementing a similar function for the BGL be reasonable? It could provide the user with a quick way to validate the outputs of shortest paths algorithm without bloating the code for dijkstra.
Best, Harry _______________________________________________ Boost mailing list -- boost@lists.boost.org To unsubscribe send an email to boost-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost@lists.boost.org/message/EAGWBBNZ...