https://svn.boost.org/trac10/ticket/4852 <p> In this page: <a href="http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths.html">http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths.html</a> and this page: <a href="http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html">http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html</a> </p> <p> you say that "The time complexity is O(V log V)". </p> <p> 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. </p> <p> According to Wikipedia: <a class="ext-link" href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time"><span class="icon">​</span>http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time</a> , the running time is O(E + V log V) if you use a Fibonacci heap. </p> <p> Also, note that in this page: <a href="http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html">http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html</a> </p> <p> 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!}</p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/4852 Trac 1.4.3 Daniel James Sat, 13 Nov 2010 19:15:09 GMT https://svn.boost.org/trac10/ticket/4852#comment:1 https://svn.boost.org/trac10/ticket/4852#comment:1 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Matias Capeletto</span> to <span class="trac-author">Andrew Sutton</span> </li> <li><strong>component</strong> <span class="trac-field-old">Documentation</span> → <span class="trac-field-new">graph</span> </li> </ul> Ticket Jeremiah Willcock Wed, 01 Dec 2010 20:15:52 GMT https://svn.boost.org/trac10/ticket/4852#comment:2 https://svn.boost.org/trac10/ticket/4852#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/66960" title="Fixed complexity of Dijkstra's algorithm; fixes #4852">[66960]</a>) Fixed complexity of Dijkstra's algorithm; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/4852" title="#4852: Bugs: Wrong complexity of Dijkstra algorithm (closed: fixed)">#4852</a> </p> Ticket