不好意思，這篇藉著前人的文來問第二小題，第二小題我看網友的答案是O(V^2)，但我自
己後來推了幾次，到現在還是覺得Loser Tree可以用來當Priority Queue(V個Run，E個Da
ta，建樹：O(V)，找最小找到結束：O(ElogV))
這個樣子的話Extract-min(Q)就可以由一般的搜尋V*V降到V*logV，DcreaseKey總共則是E
logV(如果演算中不用任何DecreaseKey，我認為是O((V-1)*2E)=O(VE)，意即每次跑新的
點要更新cost陣列時都要全部2E條邊跑一遍)
以上是小弟想法，還請教各位演算神人的指導，感謝！
※ 引述《cschenptt (chen)》之銘言：
: 題目：
: https://i.imgur.com/jZlEzBr.png
: 我的想法：
: https://i.imgur.com/JDGuqyF.jpg
: 謝謝大家

Array decrease key 也是O(1)

1. E=O(V^1.5) => O(V^2.5) ?2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV)我的想法也是這樣

第一題因為 findmin 是 O(n), decreasekey 是 O(1)所以複雜度應該是 O(|V|*n + |E| * 1) = O(nV) = (V^2)

Decrease Key 用Fib.heap才是O(1)?