[商管] 104北大資結

看板Grad-ProbAsk作者 (andrew)時間8年前 (2017/02/16 17:20), 編輯推噓1(1推 0噓 7→)
留言8則, 2人參與, 最新討論串1/1
http://i.imgur.com/uaBTJ9F.jpg
請問第六題的Dijkstra's演算法 給了兩個表 左邊是邊權重表 右邊是權重佇列表 不懂右邊表的功用 a小題是要直接利用edge-weighted圖 找出最小的連結刪除 還是是利用權重佇列圖 搞不清楚這兩個表的用意 麻煩各大大幫忙解惑！感謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.104.190 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1487236804.A.61B.html
推
02/16 23:15, , 1F
右邊就只是記錄距離值跟由哪個邊得到的而已
02/16 23:15, 1F
→
02/16 23:17, , 2F
(a) dijkstra是一直移除d值最小者且relax 第二個點d值為6
02/16 23:17, 2F
→
02/16 23:17, , 3F
在他之前的就是d值比他小的
02/16 23:17, 3F
→
02/16 23:17, , 4F
但這題目是不是錯了啊...應該是以3為起點
02/16 23:17, 4F
→
02/16 23:19, , 5F
(b) 就是下一次會選出v4 查左表對v4出去之邊relax
02/16 23:19, 5F
→
02/16 23:21, , 6F
你可以再去看一下dijkstra怎麼跑的 他不是取最小邊 是取
02/16 23:21, 6F
→
02/16 23:21, , 7F
最小d值的點
02/16 23:21, 7F
→
02/17 15:26, , 8F
好的!謝大大!!!
02/17 15:26, 8F
‣ 更多 msps50807 的文章
文章代碼(AID): #1OfMx4OR (Grad-ProbAsk)