Prim和Dijkstra算法的區別

在圖論中，Prim算法是計算最小生成樹的算法，而Dijkstra算法是計算最短路徑的算法。二者看起來比較類似，因為假設全部頂點的集合是V，已經被挑選出來的點的集合是U，那麽二者都是從集合V-U中不斷的挑選權值最低的點加入U。

二者的不同之處在於“權值最低”的定義不同，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，也就是二者直接連線的長度。