[理工] 101交大資演 mst &dijkstra

看板Grad-ProbAsk作者 (狗貓咪)時間4年前 (2021/12/26 14:39), 編輯推噓0(0推 0噓 18→)
留言18則, 2人參與, 4年前最新討論串1/1
https://i.imgur.com/B1gWYNJ.jpg
https://i.imgur.com/oFuZGxZ.jpg
想請問這題code內while loop裡面有個v=1 是否是讓in[i]都等於true的時候可以跳到1開始？ 但這樣為什麼要跳到1不跳到其他的vertex 謝謝 ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1640500747.A.B77.html
→
12/26 15:34, 4年前 , 1F
v要選其他也可以啊，只是你loop就要from 1 ~ n，
12/26 15:34, 1F
→
12/26 15:34, 4年前 , 2F
反正就是找當前dist最小的做為下次加入MST的點，
12/26 15:34, 2F
→
12/26 15:34, 4年前 , 3F
我反而覺得是下面一行要改成dist = distance[v]啦
12/26 15:34, 3F
→
12/26 15:48, 4年前 , 4F
Distance[i]這個不是loop i 過去找最小的嗎？ 為什
12/26 15:48, 4F
→
12/26 15:48, 4年前 , 5F
麼要改成distance[v]呢？
12/26 15:48, 5F
→
12/26 16:02, 4年前 , 6F
我是指v=1下面那行的dist要改，它的初始值不該是MAX
12/26 16:02, 6F
→
12/26 16:02, 4年前 , 7F
INT
12/26 16:02, 7F
→
12/26 16:03, 4年前 , 8F
loop裡面沒問題
12/26 16:03, 8F
→
12/26 16:47, 4年前 , 9F
如果他的初始值是MAXINT好像不會影響到找最小distan
12/26 16:47, 9F
→
12/26 16:47, 4年前 , 10F
ce[i]? 就算沒找到dist這個變數也不會再用到了 想請
12/26 16:47, 10F
→
12/26 16:47, 4年前 , 11F
問為什麼應該改成distance[v]呢？
12/26 16:47, 11F
→
12/26 17:42, 4年前 , 12F
假設此時node 1跟另一個node k都還沒被加入MST，且
12/26 17:42, 12F
→
12/26 17:42, 4年前 , 13F
滿足distance[1] < distance[k] < MAXINT
12/26 17:42, 13F
→
12/26 17:42, 4年前 , 14F
所以如果dist一開始設為MAXINT而非distance[v]
12/26 17:42, 14F
→
12/26 17:42, 4年前 , 15F
(或distance[1])，那麼最後v會被更新成k
12/26 17:42, 15F
→
12/26 17:42, 4年前 , 16F
，但此時應當選node 1
12/26 17:42, 16F
→
12/26 17:47, 4年前 , 17F
如果他loop硬要從2開始的話
12/26 17:47, 17F
→
12/26 17:47, 4年前 , 18F
從1就沒差啦，反正就是陣列中找最大最小值的算法
12/26 17:47, 18F
‣ 更多 pipiLUANAIAI 的文章
文章代碼(AID): #1Xo0uBjt (Grad-ProbAsk)