[问题] 最短路径花O(E) wsx02 PTT批踢踢实业坊

[问题] 最短路径花O(E)

楼主: wsx02 2012-10-30 20:52:03

http://ppt.cc/ltEM
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

谢谢

继续阅读

Re: [问题] 中序语法如何转后序语法 ?aioio1 Re: [问题] 中序语法如何转后序语法 ?space5 [问题] 中序语法如何转后序语法 ?aioio1 Re: [问题] Interview street: zombie marchneutrino [问题] 时间复杂度keke0421 [问题] Interview street: zombie marchshaopin Re: [问题] UVA 120LPH66 [问题] UVA 120keke0421 Re: [问题] ACM 11773 King’s WishCCWck [问题] ACM 11773 King’s WishBombCat