http://www.keittlab.org/
On Wed, Oct 21, 2015 at 6:26 AM, alex
Dear all, this mail concerns this pull request:
https://github.com/boostorg/graph/pull/13
which is currently over one year long. Maybe, the idea of the patch is unclear or needs some additional discussion.
I think it does.
The idea of your patch is to be able to specify a maximum distance for each node. As long as the graph distance is above that maximum distance the node does not get added to the queue. I can see that is useful, but it is not Dijkstra's algorithm. Could you just make your own function dijkstra_with_max_node_distance() or something like that?
That would be my suggestion as well. THK
The patch solves the problem which arises when using no_init version on dijkstra algorithm and passing a custom distance_map. This algorithm is implemented as call to BFS, which is very unfortunate since it is not BFS. Maybe BFS could be seen as special case of dijkstra with custom priority queue but not the other way around.
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.
The current implementation introduces some inefficiencies, which are described in the pull request's comment.
I've created very short and direct patch which makes the implementation straight forward.
It does not really seem short as it is duplicating most of the BFS code.
Additionally, the unit test is added to check mentioned efficiency gain.
It is efficient for another problem than Dijkstra's.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost