[問題] 最短路徑花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