id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
4852	Wrong complexity of Dijkstra algorithm	erelsgl@…	Andrew Sutton	"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!

"	Bugs	closed	To Be Determined	graph	Boost 1.44.0	Problem	fixed