作者pipiLUANAIAI (狗貓咪)
看板Grad-ProbAsk
標題[理工] 101交大資演 mst &dijkstra
時間Sun Dec 26 14:39:05 2021
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1640500747.A.B77.html
1F：→ chengweihsu: v要選其他也可以啊，只是你loop就要from 1 ~ n， 12/26 15:34
2F：→ chengweihsu: 反正就是找當前dist最小的做為下次加入MST的點， 12/26 15:34
3F：→ chengweihsu: 我反而覺得是下面一行要改成dist = distance[v]啦 12/26 15:34
4F：→ pipiLUANAIAI: Distance[i]這個不是loop i 過去找最小的嗎？ 為什 12/26 15:48
5F：→ pipiLUANAIAI: 麼要改成distance[v]呢？ 12/26 15:48
6F：→ chengweihsu: 我是指v=1下面那行的dist要改，它的初始值不該是MAX 12/26 16:02
7F：→ chengweihsu: INT 12/26 16:02
8F：→ chengweihsu: loop裡面沒問題 12/26 16:03
9F：→ pipiLUANAIAI: 如果他的初始值是MAXINT好像不會影響到找最小distan 12/26 16:47
10F：→ pipiLUANAIAI: ce[i]? 就算沒找到dist這個變數也不會再用到了 想請 12/26 16:47
11F：→ pipiLUANAIAI: 問為什麼應該改成distance[v]呢？ 12/26 16:47
12F：→ chengweihsu: 假設此時node 1跟另一個node k都還沒被加入MST，且 12/26 17:42
13F：→ chengweihsu: 滿足distance[1] < distance[k] < MAXINT 12/26 17:42
14F：→ chengweihsu: 所以如果dist一開始設為MAXINT而非distance[v] 12/26 17:42
15F：→ chengweihsu: (或distance[1])，那麼最後v會被更新成k 12/26 17:42
16F：→ chengweihsu: ，但此時應當選node 1 12/26 17:42
17F：→ chengweihsu: 如果他loop硬要從2開始的話 12/26 17:47
18F：→ chengweihsu: 從1就沒差啦，反正就是陣列中找最大最小值的算法 12/26 17:47