Hello, consider the follwoing Graph: struct EP { double weight; }; typedef boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, boost::no_property, EP > Graph; The call of dijkstra_shortest_paths is clear to me on that graph: boost::dijkstra_shortest_paths( m_graph, a_start_idx, weight_map( m_weight_map ).distance_map( &distance_vector[0]).predecessor_map( &parent_vector[0] ) ); where parent_vector and distance_vector are plain std::vector of the according size. Over time, I have to remove the "oldest" edges and vertices with lower index via remove_vertex() and remove_edge() from the graph and add some "newer" edges and vertices to the graph. My problem is, that the dijkstra_shortest_paths method dosen't work when I provide a plain std::vector to the distance_map() and predecessor_map() parameter of the dijkstra_shortest_paths call because of the mapping from the vertex descriptor to position in the vector. Can anybody tell me how to provide the "right" type of parameter for distance_map() and predecessor_map() ? Maybe something like boost::property_map< Graph, double EP::*>::type m_weight_map = boost::get( &EP::weight, graph ); that I'm already have done for the weight_map parameter but I'm looking for something that can handle the mapping stuff of vertex descriptors correctly. Performance is not a subject because of a few hundred vertices and edges. I'm on Boost 1.39. Kindly, Ingo