[理工] 關於Dijkstra演算法

看板Grad-ProbAsk作者 (廢文s56)時間8年前 (2017/02/05 15:43), 編輯推噓0(0推 0噓 1→)
留言1則, 1人參與, 最新討論串1/1
當在計算Dijkstra的時間複雜度時，常常會舉使用Fibbonaci heap實作 能達到最快的(E+VLOGV)速度，原因是後者的decrease只需要O(1)時間 但是decrease完值不就不一樣了嗎，那最短路徑怎麼會跟原本的一樣?感覺 這個fibbonaci heap完全想不通是怎麼運作的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.227.152 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486280627.A.709.html
→
02/05 15:45, , 1F
先複習什麼是relax吧
02/05 15:45, 1F
‣ 更多 feiwens5566 的文章
文章代碼(AID): #1ObjUpS9 (Grad-ProbAsk)