Hi Alex and all, Examine Vertex vis.examine_vertex(u, g) void This is invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u. "Examine" seems to work once on first encounter (is that correct??) so might worth a try. I did try the code below but I got errors on the part the works with the color map. Any ideas? class dijkstra_2step : public boost::default_dijkstra_visitor { public: dijkstra_2step(std::vector<Weight> dists, double threshold): distances(dists), threshold(threshold) {} void examine_vertex(boost::graph_traits <unGraph>::vertex_descriptor u, const unGraph& g){ boost::property_map< unGraph, boost::vertex_color_t >::type colorMap = boost::get(boost::vertex_color, g); if( distances[u] > threshold ) colorMap[u] = boost::color_traits::black(); } std::vector<Weight> distances; double threshold; }; Thanks