On Mon, 22 Oct 2012, Jan Hudec wrote:
Hello All,
Writing special variant of dijkstra's algorithm I wanted to reuse the `relax` function (from boost/graph/relax.hpp) that is used by dijkstra_shortest_paths_no_color_map. And I've notices what I think is mismatch in behaviour between relax and dijkstra_shortest_paths_no_color_map.
When the graph is not oriented, the relax function will consider decreasing distance of either target (obiously) or source. However it returns the same true in both cases, so the caller does not know which vertex was updated and the dijkstra_shortest_paths_no_color_map does not expect having to update the source at all. It shouldn't happen, but than why is that condition there?
It appears to me that one or the other is wrong. But I don't know the code well enough to tell which.
I'm not sure -- it might be because the code does not trust which direction of edge it will get traversing the incident edges of a vertex in an undirected graph, so the code allows some of them to be backwards (pointing from the target to the source). You can assume that a return of "true" from relax means that whichever vertex is opposite to the one that you are currently visiting the neighbors of is the one that has been updated. -- Jeremiah Willcock