Modify

Opened 7 years ago

Closed 7 years ago

#4852 closed Bugs (fixed)

Wrong complexity of Dijkstra algorithm

Reported by: erelsgl@… Owned by: asutton
Milestone: To Be Determined Component: graph
Version: Boost 1.44.0 Severity: Problem
Keywords: Cc:

Description

In this page: http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths.html and this page: http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html

you say that "The time complexity is O(V log V)".

However, any shortest-paths algorithm must, at the worst case, visit each edge at least once, so the worst-case time complexity must contain a term that depends on E.

According to Wikipedia: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time , the running time is O(E + V log V) if you use a Fibonacci heap.

Also, note that in this page: http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html

you say that for a DAG, "The time complexity is O(V + E)", and it is generally more efficient than Dijkstra's algorithm. However, in the worst case, E might be O(V2), which is worst than V log V!

Attachments (0)

Change History (2)

comment:1 Changed 7 years ago by danieljames

  • Component changed from Documentation to graph
  • Owner changed from matias to asutton

comment:2 Changed 7 years ago by jewillco

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

(In [66960]) Fixed complexity of Dijkstra's algorithm; fixes #4852

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.