实现Dijkstra的算法 [英] Implementing Dijkstra's Algorithm
问题描述
我已经完成了任务（coursework @ university）来实现一种路径寻找的形式。现在，在规范，我可以只实现一个暴力，因为有搜索的节点数量上的限制（开始，两个在中间，结束），但我想重用这个代码，来实现< a href =http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm =nofollow> Dijkstra的算法。
ve看到的伪维基百科和一个朋友写了一些为我，但它平展没有意义。这个算法看起来很简单，它不是一个问题我明白它，但我只是不能为我的生活可视化的代码，将实现这样的事情。
任何建议/提示？
编辑某些混淆：
是的，有一个目标节点和一个源节点。
我想在一般情况下实现Dijkstra，而不是只有两个中间停靠的情况，因为我想再次使用代码。否则，我只是写一个强力实现。
我有一点麻烦的具体问题是存储次优的半成型路径，以防它们可能变得最佳。当我访问一个给定的节点，我只是不知道我将如何更新所有的连接通过它。
更多编辑：
通过一个
真正的编辑：
我忘了提及一个严重的并发症，这是任何两个顶点可以具有UINT_MAX之间不同的距离。抱歉。事实上，我忘了处理这个事实可能是造成这个问题的原因首先，虽然解决方案：选择最短的幸运是显然对我。难怪其他人的伪距离变量没有考虑到我的变量距离。
Dijkstra的算法：
您将所有顶点粘贴在优先级队列中，其中所有顶点具有无穷大的优先级（距离），除非源顶点，它的距离为零（源顶点距离它自己的距离为零单位，对吧？）。
弹出优先级队列。删除的顶点是距离源最短距离的顶点。显然，从队列弹出的第一个顶点是源。好的调用，弹出顶点。
查看 v 的每个邻居。所有人都有一个大于 v 的距离（否则我们已经从队列中弹出他们，对吗？）。假设 v 的距离为3，而且 v 有3个邻接 x （dist-from-source：5）， y （dist-from-source：10）and z （dist-from-source：infinity）。
在距离 v 的每个邻居距离。让我们假设它们是： x - 3， y - 2， z - 4.这意味着从源到< x 的距离为| v | + 3（3 + 3 = 6），y 具有5（3 + 2 = 5）的距离，z具有7（3 + 4 = 7）的距离。 b
$ b
到 x 到 v 的路径比到 x 的当前最短路径长，所以我们忽略它。然而，通过 v 的 y 和 z 的路径比之前已知的最短路径短，因此我们更新它们。
你一直这样做，直到你经过所有的顶点。在每个点，当你从优先级队列弹出最小值时，你知道你已经找到了到该顶点的最短路径，因为任何可能的较短路径必须通过一个距离小于 v 的顶点，这意味着我们已经从队列中弹出。
I've been tasked (coursework @ university) to implement a form of path-finding. Now, in-spec, I could just implement a brute force, since there's a limit on the number of nodes to search (begin, two in the middle, end), but I want to re-use this code and came to implement Dijkstra's algorithm.
I've seen the pseudo on Wikipedia and a friend wrote some for me as well, but it flat out doesn't make sense. The algorithm seems pretty simple and it's not a problem for me to understand it, but I just can't for the life of me visualize the code that would realize such a thing.
Any suggestions/tips?
Edit for some confusions:
Yes, there is a target node and a source node.
I'm looking to implement Dijkstra's in a general case, not the "only two intermediate stops" case, because I want to use the code again afterwards. Else, I'd just write a brute-force implementation.
The specific issue that I'm having a little trouble with is storing the sub-optimal half-formed paths, in case they may become optimal. When I'm visiting a given node, I just don't see how I'm going to update all the connections that go through it.
More edit:
Going through a couple of the answers now and having a go.
REALLY EDIT: I forgot to mention a serious complication, which is that any two vertices can have up to UINT_MAX different distances between them. Sorry. Infact, the fact that I forgot to deal with this is probably the cause of the damn problem in the first place, although the solution: pick the shortest is fortunately obvious to me. No wonder other people's pseudo for a distance variable didn't take into account my variable distance.
Here's a high level breakdown of Dijkstra's algorithm:
You stick all of the vertices in a priority queue where all of the vertices have a priority (distance) of infinity except for the source vertex, which has a distance of zero (the source vertex is zero units of distance away from itself, right?).
Pop the priority queue. The vertex removed is the vertex with the shortest distance from the source. Obviously the first vertex popped from the queue is the source. Well call that popped vertex v.
Look at each of the neighbors of v. All of them will have a distance greater than v's distance (otherwise we would have already popped them from the queue, right?). Let's say v has a distance of 3, and v has 3 neighbors x (dist-from-source: 5), y (dist-from-source: 10) and z (dist-from-source: infinity).
Now we look at each neighbors distance from v. Let's say they are: x - 3, y - 2, z - 4. This means that the path from the source to x that goes through v has a distance of |v| + 3 (3 + 3 = 6), y has a distance of 5 (3 + 2 = 5) and z has a distance of 7 (3 + 4 = 7).
The path to x through v is longer than the current shortest path to x so we ignore it. However the paths to y and z that go through v are shorter than the previous known shortest path so we update them.
You keep doing this until you have gone through all the vertices. At each point, when you pop the min from the priority queue you know you have found the shortest path to that vertex because any possible shorter path must pass through a vertex with a distance less than v's, which means we would have already popped that from the queue.
这篇关于实现Dijkstra的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
