作者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/cn.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