[理工] 資結 Dijstra algo 找MST?

[showyoulovex (NONO)]

想問一下dijkstra's  是否能找最小生成樹

之前我是認為不行 結果有寫過題目說可以

昨天在寫考古題 答案又說不行@@

想問一下 到底可不可以呢?

感謝~祝各位考試順利

--
→ startlequiet:1080的兩倍是3160好嗎..你數學實在...
推 alwaysOGC:1F的數學老斯請假了嗎?
推 storyf66014:一樓的數學讓我好shack  XD
你們的國文老師、英文老師跟數學老師都請假了嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.110.121
推 suhorng:1<->2, w = 3;    1<->3, w = 4;    2<->3, w = 2
→ suhorng:求以 1 為起點到其他點最短路, 以及 MST
推 shenevol:dij其實是prim的延伸變形阿
所以樓上兩位大大是dij可以找MST嗎? 有點急麻煩了
※ 編輯: showyoulovex    來自: 59.117.163.159       (02/18 20:40)
推 zientsc:不行喔   以s大的例子 dij找到的cost=7 但MST的cost=5
→ showyoulovex:感謝各位~