Modify

Opened 7 years ago

Closed 7 years ago

#4852 closed Bugs (fixed)

Wrong complexity of Dijkstra algorithm

Reported by: erelsgl@… Owned by: Andrew Sutton
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 Daniel James

Component: Documentationgraph
Owner: changed from Matias Capeletto to Andrew Sutton

comment:2 Changed 7 years ago by Jeremiah Willcock

Resolution: fixed
Status: newclosed

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Andrew Sutton.
The resolution will be deleted.

Add Comment


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

 
Note: See TracTickets for help on using tickets.