我可以使用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开始,您可以通过Prim选择边缘0-1和0-2来制作树.或者,您可以选择边缘0-1和1-2来制作树.在第一个边集下,您可以找到从0到2的最小长度路径,但在第二个边集下,您将找不到最小路径.由于您无法先验确定在Prim算法中添加哪些边,因此您无法使用它来查找最短路径.

您可以考虑Bellman-Ford算法,但除非您处理负边缘权重,否则我会发现Dijkstra算法更可取.