我可以使用 Prim 的算法代替 Dijkstra 的算法来找到最短路径吗？

发布于 2024-10-24 00:18:50 字数 368 浏览 6 评论 0原文

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

示例：

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

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

原文

I have been fighting all day in understanding Dijkstra's algorithm and implementing with no significant results. I have a matrix of cities and their distances. What I want to do is to given an origin point and a destination point, to find the shortest path between the cities.

Example:

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

I started wondering if there is an other way to solve this. What if I apply Prim's algorithm from the origin's point and then I loop through the whole tree created until I find the destination point?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

紫南 2024-10-31 00:18:50

您可以应用 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 算法更可取。

You could apply Prim's algorithm and then walk the resulting tree, but you answer may be wrong. Assume that you have a graph where each edge has the same weight. Prim's algorithm simply chooses a minimal weight edge in the set of edges that could be added to the tree. It is possible that you will not choose an edge that will lead to a shortest path between two nodes.
Assume:

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

Starting from node 0 you could, via Prim's, choose the edges 0-1 and 0-2 to make your tree. Alternately, you could pick edges 0-1 and 1-2 to make your tree. Under the first edge set, you could find the minimum length path from 0 to 2, but under the second edge set you would not find the minimal path. Since you can't a-priori determine which edges get added in the Prim algorithm, you can't use it to find a shortest path.

You could consider the Bellman-Ford algorithm, but unless you're dealing with negative edge weights I find Dijkstra's algorithm preferable.

回复收藏 0 原文

~没有更多了~