Note that in the pseudo code discovery of a vertex happens only if the new distance is less than the old distance.
No, the pseudo code is based on the implied precondition that all distances are infinity. And on that condition the pseudo code and the actual code are equivalent. Note that this implied precondition is also reflected in the description of post-conditions on the same page: "Dijkstra's algorithm finds all the shortest paths from the source vertex to every other vertex" "Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the tree" "If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source" "The shortest path weight is the sum of the edge weights along the shortest path" "At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white" None of these are upheld for a distance map with arbitrary values.
If we would go with the ideas you describe, the code would not work for arbitrary distance map. There are 2 cases:
1) All values in the distance map are inf (or are implicitly inf). 2) User provides a distance map with arbitrary values and they must be respected per pseudo code.
I disagree, I don't think case 2 is a valid case for Dijkstra's shortest paths. At the moment using it like that gives inconsistent results. I don't think the purpose of the no_init version is to allow arbitrary distance values.
As far as I understand, you want to do something specific for case 1) where we do not need to do the check in the pseudo code because we know it will always be true, right? If we did so, we need to have code that also works for case 2). Right now we just have the code for case 2) and it also works for case 1). Let me know if I misunderstood something.
If you mean Piotr's patch, yes you understood correct. If you mean the current Boost version: you misunderstood, this is just for case 1.