If you think the things I suggested above aren't enough, I am willing to adapt the algorithm so that you can have your own color map and/or queue, even in the named parameter versions.
Your suggestions fully take care of the problem of the color_map, thank you very much. For the problem of resuming, I now employ another solution that is not very elegant; I make a copy of the graph that I am working on and delete from it all the edges between black cells, while inserting edges from the origin to the gray cells with the appropriate distance. I am making a superfluous copy of my graph and create too many overheads and complications. It works now, but I think it would still be very useful if BGL could offer better support for resuming calculations. The function dijkstra_shortest_path_no_init() seems to be ideal for the purpose of resuming an interrupted dijkstra_shortest_path(). I see some issues that would need to be addressed: (1) The priority queue should not be initialized from scratch in dijkstra_shortest_path_no_init(). It could possibly be initialized from the color map or be supplied be the user as a parameter. (2). The source vertice is a parameter to dijkstra_shortest_path_no_init(). The source vertex only seems relevant to the initialization. It is a clue for the initialization of the distance map (d[s] = 0), the color map (c[s] = gray), and the priority queue (Q.assign(1, s)). (3) The same problem goes for the breadth_first_visit(). It is contradictary to supply both the initialized priority queue and the source vertex, because the source vertex is used to initialize the queue. It is not correct to start the breadth_first_visit by inserting the source vertex into the queue map and coloring it gray. (it could be black already). In practice it might not be much of an issue as processing the source vertex one more time is not too costly, but still it could be cause for errors. My proposed solution: 1. Initialize the priority queue already in dijkstra_shortest_path() 2. Don't take the source vertex as a parameter in dijkstra_shortest_path_no_init() 3. Don't take the source vertex as a parameter in breadth_first_search() 4. Add the priority queue as a parameter for dijkstra_shortest_path_no_init() 5. Provide helper functions to initialize a priority queue from: (a) single source vertex (b) color_map + distance_map. I know I see these issues from my particular user-perspective, so please take the "should's", "must's", "issues", and "incorrect's" with a grain of salt. -- Alex Hagen-Zanker -- Alex Hagen-Zanker