On Wed, Oct 21, 2015 at 9:23 AM Piotr Wygocki
Dear Alex,
Thank you for your feedback!
I can see that is useful, but it is not
Dijkstra's algorithm.
Could you give the reference to the "real" Dijkstra algorithm? We are talking about implementation detail which was not concerned at all in the original Dijkstra paper. Note, that standard dijkstra call with default distance map works exactly the same with or without my patch. IMHO, the current conception (without my patch) is caused only by using BFS abstraction. Try to modify my code to achieve previous functionality and you find it really awkward.
We should probably use the pseudo code in the documentation: http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/dijkstra_shortest_paths.... The pseudo code seems to support your assertion that a vertex should not be discovered if relaxation was not successful. So it seems that the actual implementation is not in agreement with the documentation. Do you agree with that characterization of the issue? If so, your patch does take care of the issue, but we should make sure that this is the best way to go.
This does not seem a real problem. The BFS function is well suited to Dijkstra's algorithm, perhaps the only problem is that its name is not fully appropriate.
It is important to make proper abstractions. As I previously said BFS could be expressed as Dijkstra with custom priority queue implemented as FIFO. It does not work the other way around. Dijkstra is NOT a special kind of BFS. Implementation happens to be similar, which was used in this case (which is bad IMO).
I think that the perspective here was to reuse breadth_first_visit as a traversal pattern rather than as a BFS. However, as you rightly noted, that fails for the reason that when a white vertex is uncovered, it is unconditionally inserted into the queue. I've been staring at the code trying to come up with a workaround while keeping breadth_first_visit, but it quickly becomes inelegant and defeats the purpose. I think that unless we make some modifications to breadth_first_search, we may have to go with your patch. The only thing I am not sure of is this: https://github.com/boostorg/graph/pull/13/files#diff-55abe8912b7c5c01b7be025... This branch seems to be for testing purposes only to avoid using a relaxed heap, no? In any case, commenting out this if statement should probably be a separate patch with a separate explanation anyway. Does anyone have any ideas on whether there are better solutions than Piotr's patch?
Regards,
Piotr
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost