I managed to create a visitor now, however, instead of speeding things up dijkstra_shortest_paths now runs several orders of magnitudes slower! I created the visitor according to the bfs_name_printer example in the BGL User Guide and Reference Book page 11. ----- class dijkstra_finish : public Exception { }; template<unsigned maxdist> class MyVisitor : public default_dijkstra_visitor { public: MyVisitor(const vector<unsigned> &d_) : d(d_) {} template <typename Vertex, typename Graph> void finish_vertex(Vertex u, Graph g) { if (d[u]> maxdist) throw dijkstra_finish(); } private: const vector<unsigned> &d; }; struct Distance { unsigned d; }; int main() { vector<unsigned> dists(num_edges(g)); MyVisitor(dists); try { dijkstra_shortest_paths(g,source_vertex,weight_map(get(&Distance::d,g)).distance_map(make_iterator_property_map(dists.begin(),get(vertex_index,g))).visitor(vis2)); } catch(const dijkstra_finish&) {} } ----- The code seems to do what I want, all dists are either 0,1,2,3 or numeric_limits<unsigned>::max(). But for a graph with 15000 edges it takes a few ms to run dijkstra without a visitor but with it it takes 14 seconds. What am I doing wrong?