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(V^{2), 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