楼主:
wsx02 2012-10-30 20:52:03http://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)呢?
谢谢