On Tue, 6 Jul 2010, Alex Hagen-Zanker wrote:
The problem of resuming a dijkstra_shortest_path calculation is solved and I thought to share the solution here.
It works now without making a copy of the input graph and without permanently modifying the graph as I wrote earlier.
The color map is used to make a list of gray vertices (i.e. those vertices in the queue). Before resuming using dijkstra_shortest_path_no_init edges are inserted that connect the source to the gray vertices (i.e. they will be lined up to be put in the queue again). The distance of these edges is the same as the vertex distance of the gray vertices. Subsequently the gray vertices are colored white (i.e. marked as if not in the queue yet).
The effect of these actions is that the gray vertices will be inserted into the priority queue by the breadth_first_visit() at their appropriate distance.
After the dijkstra_shortest_path_no_init, it is necessary to clean up the introduced edges. There is some overhead to deal with the case that there are already edges between the gray vertices and the origin. Also there is some overhead to make sure that tentative distances and predecessors are not retained, but that is not essential.
My code is below, it is not as generic as the BGL though.
That seems like it's a complicated workaround. Did the ideas of just doing your work in a Dijkstra visitor callback (and the algorithm then resuming automatically) or using a separate thread not work for you? Those would seem to be much simpler than what you're doing. Otherwise, we don't have a good way to resume algorithms, although it has been on the TODO list for a long time. I might be able to put something simple together for you that works more directly for resumption. -- Jeremiah Willcock