4

我整天都在努力理解 Dijkstra 的算法并实施，但没有取得显著成果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。

例子：

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

我开始想知道是否有其他方法可以解决这个问题。如果我从原点应用 Prim 算法，然后循环遍历创建的整个树，直到找到目标点会怎样？

4

1 回答 1

5

您可以应用 Prim 的算法，然后遍历生成的树，但您的回答可能是错误的。假设您有一个图，其中每条边具有相同的权重。Prim 的算法只是在可以添加到树的边集中选择一个最小权重边。您可能不会选择会导致两个节点之间的最短路径的边。认为：

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

从节点 0 开始，您可以通过 Prim 选择边 0-1 和 0-2 来制作树。或者，您可以选择边缘 0-1 和 1-2 来制作您的树。在第一个边集下，您可以找到从 0 到 2 的最小长度路径，但在第二个边集下，您将找不到最小路径。由于您无法先验确定在 Prim 算法中添加了哪些边，因此您无法使用它来找到最短路径。

您可以考虑使用Bellman-Ford算法，但除非您处理负边权重，否则我发现 Dijkstra 的算法更可取。

于 2011-03-20T17:42:26.977 回答