在圖論中，Prim算法是計算最小生成樹的算法，而Dijkstra算法是計算最短路徑的算法。二者看起來比較類似，因為假設全部頂點的集合是V，已經被挑選出來的點的集合是U，那么二者都是從集合V-U中不斷的挑選權值最低的點加入U，那么二者是否等價呢？也就是說是否Dijkstra也可以計算出最小生成樹而Prim也可以計算出從第一個頂點v0到其他點的最短路徑呢？答案是否定的，否則就不必有兩個算法了。

二者的不同之處在于“權值最低”的定義不同，Prim的“權值最低”是相對于U中的任意一點而言的，也就是把U中的點看成一個整體，每次尋找V-U中跟U的距離最小（也就是跟U中任意一點的距離最小）的一點加入U；而Dijkstra的“權值最低”是相對于v0而言的，也就是每次尋找V-U中跟v0的距離最小的一點加入U。

一個可以說明二者不等價的例子是有四個頂點(v0, v1, v2, v3)和四條邊且邊值定義為(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的圖，用Prim算法得到的最小生成樹中v0跟v1是不直接相連的，也就是在最小生成樹中v0v1的距離是v0->v2->v3->v1的距離是27，而用Dijkstra算法得到的v0v1的距離是20，也就是二者直接連線的長度。

轉載于:https://www.cnblogs.com/huiliu/archive/2011/04/15/2017228.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Prim和Dijkstra算法的区别的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。