Modify

Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#4731 closed Bugs (fixed)

Documentation for dijkstra shortest path is wrong

Reported by: Markus Pilman <mpilman@…> Owned by: asutton
Milestone: To Be Determined Component: graph
Version: Boost 1.44.0 Severity: Problem
Keywords: bgl graph dijaksta shortest path minimum spanning tree Cc:

Description

In the documentation for dijkstra_shortest_paths, you can read:

"The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree."

I would say, that this is wrong: Dijkstra won't give you a minimum spanning tree in all cases.

One counterexample would be a undirected graph with the vertices (0,1,2) and the following edges (format is start,point, endpoint, weight):

(0, 1, 2) (0, 2, 3) (1, 2, 4)

This graph has only one minimum spanning tree with the predecessors map (2,0,2) - which is what you get with prim. If you execute dijkstra shortest path on this graph, you will get (2,2,2) - and this is not a minimum spanning tree (since the weight of this tree is 7, while the weight of the minimum spanning tree is 5).

Find attached an example which calculates both algorithms on these two graphs. I really think this should be fixed in the documentation.

Attachments (1)

bug.cpp (1.1 KB) - added by Markus Pilman <mpilman@…> 7 years ago.
Implementation of the example described in the bug report

Download all attachments as: .zip

Change History (7)

Changed 7 years ago by Markus Pilman <mpilman@…>

Implementation of the example described in the bug report

comment:1 Changed 7 years ago by asutton

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.

comment:2 Changed 7 years ago by asutton

  • Resolution set to fixed
  • Status changed from new to closed

comment:3 Changed 7 years ago by andresbuehlmann@…

  • Resolution fixed deleted
  • Status changed from closed to reopened

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)

comment:4 Changed 7 years ago by asutton

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.

comment:5 Changed 7 years ago by jewillco

  • Resolution set to fixed
  • Status changed from reopened to closed

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

comment:6 Changed 7 years ago by jewillco

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

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain asutton.
The resolution will be deleted. Next status will be 'reopened'.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.