[理工] 資結-100政大

看板Grad-ProbAsk作者 (hypocrisy*)時間14年前 (2012/02/04 00:21), 編輯推噓9(9推 0噓 22→)
留言31則, 11人參與, 最新討論串1/1
Which of the following data structure is the least likely to be used in Dijkstra's shortest path algorithm? (a) heap (b)queue (c)stack (d)hashing 答案是(a) 他的 Extract-min(Q)不是就是用heap維持的嗎@@? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.130.32
推
02/04 01:51, , 1F
dijkastra並沒有extract min阿
02/04 01:51, 1F
→
02/04 01:52, , 2F
每次所要取min的那陀東西都不一樣 沒必要特別用heap去連續
02/04 01:52, 2F
→
02/04 01:52, , 3F
取min 因為取一次 下一次要看的東西又不一樣了
02/04 01:52, 3F
→
02/04 01:53, , 4F
應該說 "可能"不一樣
02/04 01:53, 4F
→
02/04 02:32, , 5F
有吧@@? 不是時間複雜度還有分兩種case:heap和Fib.Heap
02/04 02:32, 5F
→
02/04 02:33, , 6F
heap是O(ElogV) Fib.Heap是O(E+VlogV)
02/04 02:33, 6F
→
02/04 02:38, , 8F
Running Time那邊也有寫我上面講的那些
02/04 02:38, 8F
→
02/04 08:10, , 9F
天哪 為啥會有 奇怪了
02/04 08:10, 9F
→
02/04 09:26, , 10F
有用heap取最小阿 這題真的很怪...答案應該d吧
02/04 09:26, 10F
推
02/04 09:37, , 11F
印象中這題好像要改成mist likely to
02/04 09:37, 11F
→
02/04 09:38, , 12F
most
02/04 09:38, 12F
→
02/04 10:14, , 13F
least likely丟GOOGLE翻譯是最有可能XD
02/04 10:14, 13F
→
02/04 11:20, , 14F
考英文0.0
02/04 11:20, 14F
推
02/04 11:51, , 15F
原來是「最有可能」XDDD
02/04 11:51, 15F
推
02/04 11:55, , 16F
原來這是最有可能XD
02/04 11:55, 16F
推
02/04 13:14, , 17F
所以答案是(a)?
02/04 13:14, 17F
推
02/04 15:43, , 18F
就a吧 每次都會extract-min
02/04 15:43, 18F
推
02/04 18:36, , 19F
wtfffffff
02/04 18:36, 19F
→
02/04 23:17, , 20F
我不太懂 為啥會有extract-min?
02/04 23:17, 20F
→
02/04 23:18, , 21F
我是想說 與未標註的點 距離會一直在更新 而每次要找min
02/04 23:18, 21F
→
02/04 23:18, , 22F
來當下一個標註的點 並且在更新其他距離
02/04 23:18, 22F
→
02/04 23:19, , 23F
所以應該每次都要重新 scan與標註點群 鄰近的點 距離吧
02/04 23:19, 23F
推
02/05 00:32, , 24F
你說的也沒錯 距離一直更新=>一直變小 這一點可以由
02/05 00:32, 24F
→
02/05 00:33, , 25F
heap的decrease-key作成 若違反min heap特性 則bubble
02/05 00:33, 25F
→
02/05 00:33, , 26F
extract-min是Introduction to Algorithms那本課本上寫的
02/05 00:33, 26F
→
02/05 00:33, , 27F
上去 自然最上面的就是最小的
02/05 00:33, 27F
→
02/05 00:35, , 28F
也就是說你說的步驟用priority queue可以幫你作好
02/05 00:35, 28F
→
02/05 00:36, , 29F
在cormen p595 第二版
02/05 00:36, 29F
推
02/05 01:45, , 30F
喔喔喔 原來還有decrease-key XD
02/05 01:45, 30F
→
09/11 14:52, , 31F
//en.wikipe https://daxiv.com
09/11 14:52, 31F
‣ 更多 white8824 的文章
文章代碼(AID): #1FB0bzhu (Grad-ProbAsk)