I tried to implement the simplified code but I guess I really do not understand the Boost Graph lib.
You might find it easier to use shared_array_property_maps (I do). Try if the following works for you. typedef typename boost::graph_traits<graph_t>::vertex_descriptor vertex_type; typedef typename boost::property_map<graph_t, vertex_index_t>::type index_map_type; typedef typename boost::shared_array_property_map<int, index_map_type > distance_map_type; typedef typename boost::shared_array_property_map<vertex_type, index_map_type > predecessor_map_type; vertex_type start = 24; // or whatever vertex_type end = 13; // or whatever index_map_type vertex_id = get(vertex_index, g); distance_map_type distance(boost::num_vertices(g), vertex_id); predecessor_map_type predecessor(boost::num_vertices(g), vertex_id); boost::dijkstra_shortest_paths(g, start, boost::distance_map(distance).predecessor_map(predecessor))); std::vector<vertex_type> path; for(vertex_type current = end; current != start; current = predecessor[current] ) { path.push_back(current); } path.push_back(start); std::reverse(path.begin(), path.end());