我可以使用Prim的算法而不是Dijkstra的尋找最短路徑嗎？

Question

我已經奮鬥了一整天理解Dijkstra算法，並沒有顯著的結果執行。我有一個城市矩陣和他們的距離。我想要做的是給出一個起點和一個終點，找到城市之間的最短路徑。

例子：

 __0__ __1__ __2__ 
0 | 0 | 34 | 0 | 
    |-----|-----|-----| 
1 | 34 | 0 | 23 | 
    |-----|-----|-----| 
2 | 0 | 23 | 0 | 
    ----- ----- ----- 

我開始不知道是否有解決這個的其他方式。如果我從原點開始應用Prim算法，然後循環創建的整個樹直到找到目標點爲止？

Answer 1

您可以應用Prim算法，然後步行結果樹，但你的答案可能是錯的。假設你有一個圖形，其中每個邊具有相同的權重。 Prim的算法只是在可以添加到樹中的邊集中選擇一個最小權重邊。您可能不會選擇導致兩個節點之間的最短路徑的邊。 假設：

 __0__ __1__ __2__ 
0 | 0 | 1 | 1 | 
    |-----|-----|-----| 
1 | 1 | 0 | 1 | 
    |-----|-----|-----| 
2 | 1 | 1 | 0 | 
    ----- ----- ----- 

從節點0你可以開始，通過普里姆的，選擇的邊緣0-1和0-2，以使你的樹。或者，你可以選擇邊緣0-1和1-2來製作你的樹。在第一個邊集下，您可以找到從0到2的最小長度路徑，但在第二個邊集之下，您將找不到最小路徑。由於您不能先驗地確定在Prim算法中添加了哪條邊，因此無法使用它找到最短路徑。

你可以考慮Bellman-Ford算法，但除非你正在處理負邊權，我覺得Dijkstra算法最好。