Hello, I've been writing custom version of Dijkstra's shortes path algorithm because of specific constraints and I was using the dijkstra_shortest_paths_no_color_map function as template. And I've notices that it only works by accident: The inner loop (I've had 1.51, but there is no change in trunk) goes like this: BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) { // [visitor, negative check, not interesting now] // Extract the neighboring vertex and get its distance Vertex neighbor_vertex = target(current_edge, graph); Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex); bool is_neighbor_undiscovered = !distance_compare(neighbor_vertex_distance, distance_infinity); Considering the case when the vertex is not discovered: neighbor_vertex_distance = infinity is_neighbor_undiscovered = true // Attempt to relax the edge bool was_edge_relaxed = relax(current_edge, graph, weight_map, predecessor_map, distance_map, distance_weight_combine, distance_compare); Since any sensible distance is less than infinity, the relax function will return *true*: was_edge_relaxed = true if (was_edge_relaxed) { vertex_queue.update(neighbor_vertex); So this gets executed. But the vertex is not in the queue! OOPS! The code however executes successfuly. This is because the index_in_heap property map given to the d_ary_heap_indirect is initialized to 0. But 0 is correct index pointing to top and updating top is a no-op. Correct "not-in-heap" value would be -1 (and that's what the queue stores in pop()). visitor.edge_relaxed(current_edge, graph); } else { visitor.edge_not_relaxed(current_edge, graph); } if (is_neighbor_undiscovered) { visitor.discover_vertex(neighbor_vertex, graph); vertex_queue.push(neighbor_vertex); Here finally comes the push. Obviously it should have been first. Curiously this visitor callback is called before the queue operations while the edge_relaxed above is called after. Is there any reason for this particular order of operations? (Obviously fixing the code would be easier if the order of callbacks didn't matter) } } // end out edge iteration Should this be fixed? Are there any risks doing so? -- Jan 'Bulb' Hudec <bulb@ucw.cz>