我知道Prim's和Dijkstra算法之間的區別。前者產生MST，後者產生從源到所有節點的最短路徑。在數學上，這些不一樣，所以我們並不總是期望這兩種算法產生相同的結果。Dijkstra算法和Prim算法何時會產生不同的輸出？
但是，雖然嘗試不同的例子，我得到了同樣的結果。 Prim算法和Dijkstra算法的僞碼看起來也非常相似。有人可以舉一個例子，說明普利姆公司生產的MST在與迪傑斯特拉解決時無法獲得，反之亦然。據我所知，還有一些其他的東西。這兩種算法都使用以下方法。請糾正我，如果我錯了：
尋找最短I-J，其中i從一組尚未納入尚未然後添加J任務到組已經被列入集和j 。
一個簡單的例子是放置在正方形的角四個節點的集合。將成本2的邊緣放置在任意兩個相鄰角落之間，並將成本3的邊緣對角地放置在正方形上。從任何一個角落運行Dijkstra算法將挑選這些邊緣：
* -- *
| \
| \
* *
這是最短的路徑，並且邊緣的總成本爲7
運行Prim算法將挑選這些邊緣：
* -- *
|
|
* -- *
這是一個MST（總邊緣成本爲6），但這些不是最短路徑（從左上角到右下角的路徑花費爲4，但是可能有更直接的路徑。）
視爲挑戰：儘量找圖，其中
普里姆的和Dijkstra的都被找到了一些節點不在一組，並把它納入集選擇一個節點，但他們在如何調整距離不同。在Prim算法中，使用的距離總是從集合外的任何節點到集合內的任何節點的最小距離。在Dijkstra算法中，距離是最小值以下值的：
距離（開始節點，U）+ 1（U，V）
換句話說，在距離Dijkstra算法的因素從起始節點到集外的節點，而Prim's則不。
希望這有助於！
考慮a-b長度爲100，a-c長度爲100，b-c長度爲1。以a爲根的最短路徑樹是a-b和a-c。 mst是b-c和其他邊緣之一。鏈接：Create a MST with depth-first search?。
現在我明白了，謝謝你的回答和編輯。 – nitinsh99