Ticket #4852 (closed Bugs: fixed)

Opened 5 years ago

Last modified 5 years ago

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:


In this page: and this page:

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: , the running time is O(E + V log V) if you use a Fibonacci heap.

Also, note that in this page:

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!


Change History

comment:1 Changed 5 years ago by danieljames

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

comment:2 Changed 5 years ago by jewillco

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

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


Add a comment

Modify Ticket

Change Properties
<Author field>
as closed
The resolution will be deleted. Next status will be 'reopened'

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

Note: See TracTickets for help on using tickets.