I can see that is useful, but it is not
Dijkstra's algorithm.
Could you give the reference to the "real" Dijkstra algorithm? We are talking about implementation detail which was not concerned at all in the original Dijkstra paper.
Dijkstra (1959) A Note on Two Problems in Connexion with Graphs: "If the node R belongs to set C, it is added to set B " Boost: if (v_color == Color::white()) { put(color, v, Color::gray()); Patch: if(decreased) { if (v_color == Color::white()) { put(color, v, Color::gray()); Now, I know that in the classical usage 'decreased' is always true, so there is no change in behaviour. I also know that the way that Boost implements Dijkstra, it evaluates 'decreased' anyway despite knowing beforehand it must be true. So you are not proposing to change behaviour or to make the function less efficient. But, I think BGL shouldn't evaluate 'decreased' to begin with (https://svn.boost.org/trac/boost/ticket/7387).
Note, that standard dijkstra call with default distance map works exactly the same with or without my patch. IMHO, the current conception (without my patch) is caused only by using BFS abstraction. Try to modify my code to achieve previous functionality and you find it really awkward.
I think one solution would be to use a visitor with a reference to the queue and to a map indicating precalculated nodes. You could then use the edge_relaxed() callback with void edge_relaxed(G& , E& e) { Vertev t = target(e); if( get(is_precalculated, t ) { queue.push(t) put(is_precalculated, t, false); } To use this you would need to initialize the color_map such that the color for precalculated nodes is gray.
This does not seem a real problem. The BFS function is well suited to Dijkstra's algorithm, perhaps the only problem is that its name is not fully appropriate.
It is important to make proper abstractions. As I previously said BFS could be expressed as Dijkstra with custom priority queue implemented as FIFO. It does not work the other way around. Dijkstra is NOT a special kind of BFS. Implementation happens to be similar, which was used in this case (which is bad IMO).
To me it looks like a good abstraction with a bad name.