我的任务是（大学课程）实施某种形式的寻路。现在，在规范中，我可以实现强力，因为要搜索的节点数量有限制（开始，中间两个，结束），但我想重新使用此代码并来实现迪杰斯特拉算法 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
我在维基百科上看到了伪内容，一位朋友也为我写了一些，但它完全没有意义。这个算法看起来很简单，理解它对我来说不是问题，但我一生都无法想象实现这样的事情的代码。
有什么建议/提示吗？
编辑一些混淆：
是的，有一个目标节点和一个源节点。
我希望在一般情况下实现 Dijkstra，而不是“只有两个中间站”的情况，因为我想在之后再次使用该代码。否则，我只会编写一个强力实现。
我遇到的具体问题是存储次优的半成形路径，以防它们变得最优。当我访问给定节点时，我只是不知道如何更新通过该节点的所有连接。
更多编辑：
现在浏览几个答案并尝试一下。
真正编辑：
我忘了提到一个严重的复杂情况，即任何两个顶点之间的距离最多可达 UINT_MAX 。对不起。事实上，我忘记处理这个问题可能首先就是导致该死问题的原因，尽管解决方案：幸运的是，选择最短的对我来说是显而易见的。难怪其他人的伪距离变量没有考虑到我的可变距离。
以下是 Dijkstra 算法的高级分解：
将所有顶点放入优先级队列中，其中所有顶点的优先级（距离）均为无穷大except对于源顶点，其距离为零（源顶点与其自身的距离为零，对吗？）。
弹出优先级队列。移除的顶点是距源距离最短的顶点。显然，从队列中弹出的第一个顶点是源。我们称那个弹出的顶点为v.
看看每个邻居v。它们的距离都大于v的距离（否则我们已经把它们从队列中弹出了，对吧？）。比方说v距离为 3，并且v有 3 个邻居x（距源的距离：5），y（距源的距离：10）和z（距源的距离：无穷大）。
现在我们看看每个邻居的距离v。假设它们是：x - 3, y - 2, z- 4. 这意味着从源到的路径x那个经过v距离为 |v| + 3 (3 + 3 = 6),y距离为 5 (3 + 2 = 5)，z 距离为 7 (3 + 4 = 7)。
通往的路径x通过v比当前最短路径长x所以我们忽略它。然而，路径y and z那些经过v比之前已知的最短路径短，因此我们更新它们。
继续这样做，直到遍历完所有顶点。在每个点，当您从优先级队列中弹出最小值时，您就知道您已经找到了到该顶点的最短路径，因为任何可能的较短路径必须经过距离小于的顶点v's，这意味着我们已经将其从队列中弹出。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
