On 01.09.2016 13:25, François wrote:
Hello,
I'm exhuming this rather old thread because I came across a related thread in the boost mailing list https://groups.google.com/forum/#!topic/boost-list/7nCzvkkEXCk .
If I get right, the problem is the same that I'm dealing with. The initialization of the distance / predecessor maps takes more time than the actual Dijkstra search because a very small region of the graph is visited. I guess that it is particularly true when the distance / predecessor maps do not fit in CPU cache.
Could you go through the proposed solution? If you confirm that the solution is suitable, I'll implement it in the bfs / dijkstra visitors.
I think the simplest solution would be to let the user specify the distance and predecessor maps, as we have now, together with an "init" option, that defaults to True. If init=False, the distance and predecessor maps are assumed to be already initialized.
Best, Tiago