If I use my own colour map as you describe, Could I also colour it beforehand and not in the visitor?
From your link seem that I am in the same category of 'no_init' search so
Probably the colour map that I provide is used directly and its not 're-initialised'. That would work I think.
Now the code. Im having treble building the correct 'no_init' call. Googling around helped but not much.
Avoid using pointers as property maps, sometimes that causes problems. You could use shared_array_property_maps. typedef boost::default_color_type Color; typedef boost::color_traits<color_type> color_traits; typedef boost::shared_array_property_map<Vertex> PredecessorMap; typedef boost::shared_array_property_map<Weight> DistanceMap; typedef boost::shared_array_property_map<color_type> ColorMap; int n = boost::num_vertices(m_urgraph); IndexMap indexMap = boost::get(boost::vertex_index, m_ugraph); PredecessorMap predecessorMap(n, indexMap); DistanceMap distanceMap(n, indexMap); ColorMap colorMap(n, indexMap); Weight d_inf = std::numeric_limits<Weight>::max(); // something like this Weight d_zero = Weight(); boost::default_dijktra_visitor vis; BGL_FORALL_VERTICES(v, m_ugraph, unGraph) { // vis.initialize_vertex(v, m_ugraph); put(predecessorMap, v, v); put(distanceMap, v, d_inf); Color color = get(old_distance, v) > radius1 ? color_traits::black() : color_traits::white()); put(colorMap, v, color); } dijkstra_shortest_paths_no_init( m_ugraph, s_vertex, predecessorMap, distanceMap, boost::weight_map(boost::get(&EdgeProperties::m_metric_distance_weight, m_ugraph)), indexMap, std::less<Weight>(), boost::closed_plus<Weight>(d_inf), d_zero, vis, colorMap); Hope this helps, Alex