[问题] 最短路径花O(E)
楼主: wsx02 2012-10-30 20:52:03
CLRS的习题 请问b 他给的图是dense 题目的定义应该是边数比点数多
我的想法是用F-heap去实作Dijkstra 把摊销考虑进去
这样花V次extract-min + E次decrease-key = V*O(dlog n) + E*O(1) 吧?
d
所以O(Vdlog n + E)? 然后题目给边数比点数多 要想办法把dlog n降成常数吧?
d d
请问该怎么分析才能到O(E)呢?
谢谢
作者: stimim (qqaa) 0000-00-00 00:00:00
E+Vlogn = V(V^e + logn) = O(V*V^e) = O(E)n^k = Omega(log n) for any k > 0
楼主: wsx02 0000-00-00 00:00:00
谢谢
继续阅读