推 JiDung:dijkastra並沒有extract min阿 02/04 01:51
→ JiDung:每次所要取min的那陀東西都不一樣 沒必要特別用heap去連續 02/04 01:52
→ JiDung:取min 因為取一次 下一次要看的東西又不一樣了 02/04 01:52
→ JiDung:應該說 "可能"不一樣 02/04 01:53
→ white8824:有吧@@? 不是時間複雜度還有分兩種case:heap和Fib.Heap 02/04 02:32
→ white8824:heap是O(ElogV) Fib.Heap是O(E+VlogV) 02/04 02:33
→ white8824:Running Time那邊也有寫我上面講的那些 02/04 02:38
→ JiDung:天哪 為啥會有 奇怪了 02/04 08:10
→ whenisawu:有用heap取最小阿 這題真的很怪...答案應該d吧 02/04 09:26
推 rockmanray:印象中這題好像要改成mist likely to 02/04 09:37
→ rockmanray: most 02/04 09:38
→ Byzantin:least likely丟GOOGLE翻譯是最有可能XD 02/04 10:14
→ mqazz1:考英文0.0 02/04 11:20
推 rockmanray:原來是「最有可能」XDDD 02/04 11:51
推 DiLegend:原來這是最有可能XD 02/04 11:55
推 ste2323:所以答案是(a)? 02/04 13:14
推 rockmanray:就a吧 每次都會extract-min 02/04 15:43
推 onlyeric23:wtfffffff 02/04 18:36
→ JiDung:我不太懂 為啥會有extract-min? 02/04 23:17
→ JiDung:我是想說 與未標註的點 距離會一直在更新 而每次要找min 02/04 23:18
→ JiDung:來當下一個標註的點 並且在更新其他距離 02/04 23:18
→ JiDung:所以應該每次都要重新 scan與標註點群 鄰近的點 距離吧 02/04 23:19
推 rockmanray:你說的也沒錯 距離一直更新=>一直變小 這一點可以由 02/05 00:32
→ rockmanray:heap的decrease-key作成 若違反min heap特性 則bubble 02/05 00:33
→ n60119:extract-min是Introduction to Algorithms那本課本上寫的 02/05 00:33
→ rockmanray:上去 自然最上面的就是最小的 02/05 00:33
→ rockmanray:也就是說你說的步驟用priority queue可以幫你作好 02/05 00:35
→ rockmanray:在cormen p595 第二版 02/05 00:36
推 JiDung:喔喔喔 原來還有decrease-key XD 02/05 01:45