Re: [boost] [graph] dijkstra pull request ping

Subject: Re: [boost] [graph] dijkstra pull request ping
From: alex (alexhighviz_at_[hidden])
Date: 2015-10-23 12:49:17

> 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.