We should probably use the pseudo code in the documentation:
http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/dijkstra_shortest_paths....
The pseudo code seems to support your assertion that a vertex should not be discovered if relaxation was not successful. So it seems that the actual implementation is not in agreement with the documentation. Do you agree with that characterization of the issue?
Agreed. Alex and Tim suggested two versions of algorithm. We have already 7 versions of Dijkstra's algorithm (one is not documented), having two versions of dijkstra_no_init would introduce another two overloads. IMO this should be done only in case in which we find sensible use cases for both versions. On the other hand, this change might be breaking for some users but I expect this to happen very rarely. Regards, Piotr