On Apr 12, 2006, at 5:10 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes:
This would change the complexity of Dijkstra's algorithm from O(|V| lg |V|) to O(|V| lg |E|), where |V| is the number of vertices in the graph and |E| is the number of edges in the graph.
Hmm, did you see: http://lists.boost.org/Archives/boost/2002/01/23970.php and the foregoing thread?
I've read it now. So I'll be more careful with the complexity measures: With a relaxed heap it's O(|V| lg |V| + |E|) With a binary heap it's O((|V| + |E|) lg |V|) If you insert instead of updating, that, lg |V| becomes a lg |E|. The relaxed heap is admittedly complicated. We have some performance test's we've run, and it's a toss-up. On some graphs, the binary heap does slightly better; on others, the relaxed heap does slightly better. Doug
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost