[Boost-bugs] [Boost C++ Libraries] #4852: Wrong complexity of Dijkstra algorithm

Subject: [Boost-bugs] [Boost C++ Libraries] #4852: Wrong complexity of Dijkstra algorithm
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-11-13 18:53:44

#4852: Wrong complexity of Dijkstra algorithm
-------------------------------+--------------------------------------------
 Reporter:  erelsgl@…          |       Owner:  matias       
     Type:  Bugs               |      Status:  new          
Milestone:  To Be Determined   |   Component:  Documentation
  Version:  Boost 1.44.0       |    Severity:  Problem      
 Keywords:                     |  
-------------------------------+--------------------------------------------
 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!

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4852>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.