[商管] 104北大資結

[msps50807 (andrew)]

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
推 aa06697: 右邊就只是記錄距離值跟由哪個邊得到的而已
→ aa06697: (a) dijkstra是一直移除d值最小者且relax 第二個點d值為6
→ aa06697:  在他之前的就是d值比他小的
→ aa06697: 但這題目是不是錯了啊...應該是以3為起點
→ aa06697: (b) 就是下一次會選出v4 查左表對v4出去之邊relax
→ aa06697: 你可以再去看一下dijkstra怎麼跑的 他不是取最小邊 是取
→ aa06697: 最小d值的點
→ msps50807: 好的!謝大大!!!