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. Jeremiah, Thanks for your help! template<class TGraph> class ResumableDijkstra { public: typedef typename TGraph::vertex_descriptor TVertex; typedef typename TGraph::edge_property_type::value_type TEdge; // EDGE PROPERTY, NOT DESCRIPTOR ResumableDijkstra() : m_Graph(NULL), m_Predecessors(NULL), m_Distances(NULL), m_Colors(NULL), m_GrayVertexDistances(NULL) { m_Predecessors = new std::vector<TVertex>; m_Distances = new std::vector<double>; m_Colors = new std::vector<boost::default_color_type>; m_GrayVertices = new std::vector<TVertex>; m_GrayVertexDistances = new std::vector<double>; } ~ResumableDijkstra() { delete m_Predecessors; delete m_Distances; delete m_Colors; delete m_GrayVertices; delete m_GrayVertexDistances; } void Initialize(TGraph& graph, TVertex origin) { m_Origin = origin; m_Graph = &graph; const int nVertices = boost::num_vertices(graph); m_Distances->assign(nVertices, std::numeric_limits<double>::max()); (*m_Distances)[m_Origin] = 0; m_Colors->assign(nVertices, boost::color_traits<boost::default_color_type>::white()); m_Predecessors->resize(nVertices); for(int i = 0; i < nVertices; i++) { (*m_Predecessors)[i] = (TVertex) i; } } template<class TVis> bool Expand(const TVis& visitor) { bool finished = true; std::vector<TEdge*> restoreEdges; ModifyGraph(restoreEdges); try { boost::dijkstra_shortest_paths_no_init<TGraph, TVis>( *m_Graph, m_Origin, &((*m_Predecessors)[0]), &((*m_Distances)[0]), boost::get(&TEdge::m_Cost, *m_Graph), boost::get(boost::vertex_index, *m_Graph), std::less<double>(), boost::closed_plus<double>(), (double) 0.0, visitor, &((*m_Colors)[0]) ); } catch(AxExit) { finished = false; } RestoreGraph(restoreEdges); if(!finished) { ListGrayVertices(); } return finished; } void ModifyGraph(std::vector<TEdge*>& restoreEdges) { const int n = m_GrayVertices->size(); restoreEdges.assign(n, NULL); for(int i = 0; i < n; ++i) { if( boost::edge(m_Origin, (*m_GrayVertices)[i], *m_Graph).second ) { TEdge* e = new TEdge; *e = (*m_Graph)[boost::edge(m_Origin, (*m_GrayVertices)[i], *m_Graph).first]; boost::remove_edge(m_Origin, (*m_GrayVertices)[i], *m_Graph); restoreEdges[i] = e; } TEdge edge; edge.m_Cost =(*m_GrayVertexDistances)[i]; boost::add_edge(m_Origin, (*m_GrayVertices)[i], edge, *m_Graph); } } void RestoreGraph(std::vector<TEdge*>& restoreEdges) { const int n = (int) m_GrayVertices->size(); assert(n == (int)restoreEdges.size() ); for(int i = 0; i < n; ++i) { boost::remove_edge(m_Origin, (*m_GrayVertices)[i], *m_Graph); if( restoreEdges[i] != NULL) { boost::add_edge(m_Origin, (*m_GrayVertices)[i], *(restoreEdges[i]), *m_Graph); delete restoreEdges[i]; restoreEdges[i] = NULL; } } m_GrayVertices->clear(); m_GrayVertexDistances->clear(); restoreEdges.clear(); } void ListGrayVertices() { m_GrayVertices->clear(); m_GrayVertexDistances->clear(); const int nVertices = m_Colors->size(); for(int j = 0; j < nVertices; j++) { if((*m_Colors)[j] == boost::color_traits<boost::default_color_type>::gray() && j != m_Origin) { m_GrayVertices->push_back(j); m_GrayVertexDistances->push_back((*m_Distances)[j] ); (*m_Distances)[j] = std::numeric_limits<double>::max(); (*m_Predecessors)[j] = j; (*m_Colors)[j] = boost::color_traits<boost::default_color_type>::white(); } } } TGraph* m_Graph; std::vector<TVertex>* m_Predecessors; std::vector<double>* m_Distances; std::vector<boost::default_color_type>* m_Colors; std::vector<TVertex>* m_GrayVertices; std::vector<double>* m_GrayVertexDistances; TVertex m_Origin; };