# Boost :

Subject: [boost] [graph] dijkstra_shortest_paths_no_color_map works by accident
From: Jan Hudec (bulb_at_[hidden])
Date: 2012-10-22 15:56:58

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_at_[hidden]>
```