[理工] 演算法 Prim's Algo for MST
我想問一下要怎麼證明 Prim's Algo的正確性
如果是 Kruskal 的話 可以藉由反證法
證明出 最短的邊一定要在TREE中 反覆的LOOP而證
而Prim依我個人的見解
他的想法是來自於 Dijkstra's 的最短路徑
也就是 Set A 到 Set B 中的最短路徑
但是 Dijkstra's 有個明顯的限制是
不能有負邊存在
可是 Prim's Algo 就算圖中有邊還是可以解
我唯一想到的東西就類似
選擇連向某點的邊一定要是他的最短邊之一
但是沒能想得很清楚
有高手可以解答一下嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.62.105