Boost C++ Libraries: Ticket #4731: Documentation for dijkstra shortest path is wrong

attachment set

Wed, 13 Oct 2010 10:36:29 GMT

attachment → bug.cpp

Implementation of the example described in the bug report

Andrew Sutton — Wed, 13 Oct 2010 13:47:57 GMT

I agree. The search tree computed by SP algorithm is not guaranteed to be a MST. Updated the documentation to describe the results in terms of a "search tree" with a statement claiming that it is not guaranteed to be an MST.

Changes in r65939.

status changed; resolution set

Andrew Sutton — Wed, 13 Oct 2010 13:48:20 GMT

status new → closed
resolution → fixed

status changed; resolution deleted

andresbuehlmann@… — Thu, 14 Oct 2010 14:35:33 GMT

status closed → reopened
resolution fixed

The term "search tree" used in the current fix is misleading/imprecise depending how you define "search tree". Either use a term like "fully relaxed search tree" or another term like "spanning tree describing all shortest paths from the specified start vertex".

Observe that the spanning tree encoded in the predecessor map describes the shortest path to every vertex in the graph from the defined start vertex. This is usually NOT equal to the "search tree" describing the order in which dijkstra explored the edges (without applying relaxation to this tree).

To observe the difference between "fully relaxed search tree" and "search tree" the following example:

Given a graph on vertices {0, 1, 2} and edges (0, 1, 2), (1, 2, 4), (0, 2, 3) where the format is (start point, end point, weight).

For running dijkstra on it with start vertex 1:

The "Search tree" in my eyes would be (1, 1, 0) (to be read as the predecessor map)
The predecessor map (result of dijkstra) is: (1, 1, 1)

Andrew Sutton — Thu, 14 Oct 2010 15:38:20 GMT

It may be the case that such descriptions are more precise, but I feel that they are unnecessary. I may consider redefining it as "the tree computed by the algorithm" rather than "traversal", but I'm not going to try to be more specific.

The reason is that those specific properties of the tree are imposed by the completion of the algorithm--not guaranteed by tree itself. If the algorithm fails to complete or is terminated early, by exception for example, neither description would be correct. However, a search tree on input will still be a search tree on output, regardless of the termination state of the algorithm.

status changed; resolution set

Jeremiah Willcock — Thu, 14 Oct 2010 19:02:06 GMT

status reopened → closed
resolution → fixed

(In [65964]) Clarified docs further; fixes #4731

Jeremiah Willcock — Tue, 19 Oct 2010 15:28:59 GMT

(In [66093]) Merged changes r65193, r65939, r65963, and r65964 from trunk; refs #4731, #4737