On Fri, Oct 23, 2015 at 12:49 PM alex
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.
I don't believe in "implied" assumptions. A comment in the pseudo code says: " *This loop is not run in dijkstra_shortest_paths_no_init"* I think that there are strictly two cases, one in which the loop is run and the other in which it is not. When the loop is run, the algorithm can be optimized in the way you have described previously (i.e., the check for improvement of distance may be removed when a vertex is white).
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"
That sentence continues with "by" and the rest of the paragraph which specifies what is actually supposed to hapen.
"Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the tree"
That just says what the tree is.
"If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source"
That is probably tough. With the no_init version one can have vertices without a parent that are still reachable from source. I would not take this as restricting the possible values of the distance map in the no_init version. I think that by specifying a custom distance map, one can basically modify what is reachable and what is not.
"The shortest path weight is the sum of the edge weights along the shortest path"
That is still true, modulo the meaning of the word reachable.
"At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white"
Again, modulo reachable.
None of these are upheld for a distance map with arbitrary values.
They mostly are, except that one can make some vertices unreachable. I think that all the post-conditions you have listed here are not strong enough to forbid arbitrary values in the distance map for the no_init version of the algorithm. I myself would assume by reading the pseudo code and the documentation that there is nothing preventing me from using the no_init version of the algorithm along with a custom distance map to control traversal. I think that forbidding custom distance map at this point would not be backward compatible, but it would also be counterproductive, as there is really not a good reason to do so. If anything, the documentation should be made more unambiguous on the point of what are the possible inputs for the distance map.
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.
OK, so here we disagree. I think that this is precisely the reason for the no_init version. Why would we need it otherwise? Besides, I think that there is no reason to forbid such a usage, and this is similar to providing a preinitialized color map to BFS. The documentation is quite clear to what the algorithm actually does, and the pseudo code is not broken by allowing arbitrary distance maps as inputs. I don't see a compelling reason to forbid controlling the behavior of the algorithm by providing a custom distance map. On the other hand, if there was more voices from the users that would want to eliminate such a use, we could do that, but I am not sure how this improves the library. I do agree though that the documentation of the no_init features could be improved.
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.
This point would depend on what decision we make on the discussion above. If we allow arbitrary distance maps, then we would two versions of code to provide the optimization you propose.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost