问题标签 [dijkstra]

今天早些时候，我在欣赏《谦虚的程序员》时遇到了这个选择引用：

因此，暂时甚至可能永远，第二类规则表现为程序员要求的纪律元素。我脑海中的一些规则是如此清晰，以至于它们可以被教授，并且永远不需要争论给定的程序是否违反它们。例如，如果不提供终止证明或不说明其不变性不会因执行可重复语句而破坏的关系，则不应写下任何循环。

我正在寻找 Dijkstra 的 1300 多篇著作中的哪一篇最好地描述了他在上面描述的更详细的规则。

我的任务是（课程@大学）实施一种寻路形式。现在，在规范中，我可以只实施蛮力，因为要搜索的节点数量有限制（开始，中间两个，结束），但我想重用这段代码并来实现Dijkstra 的算法。

我在 Wikipedia 上看到了伪，一个朋友也为我写了一些，但这完全没有意义。该算法看起来很简单，理解它对我来说不是问题，但我无法终生想象实现这种事情的代码。

有什么建议/提示吗？

编辑一些混淆：
是的，有一个目标节点和一个源节点。
我希望在一般情况下实现 Dijkstra，而不是“只有两个中间停止”的情况，因为我想在之后再次使用该代码。否则，我只会写一个蛮力实现。
我遇到一点麻烦的具体问题是存储次优的半形成路径，以防它们变得最优。当我访问给定节点时，我只是看不到如何更新通过它的所有连接。
更多编辑：
现在通过几个答案并试一试。

真正的编辑：我忘了提到一个严重的并发症，即任何两个顶点之间最多可以有 UINT_MAX 不同的距离。对不起。事实上，我忘记处理这个事实可能首先是导致该死问题的原因，尽管解决方案：选择最短的对我来说是幸运的。难怪其他人对距离变量的伪没有考虑到我的变量距离。

我想将以下图形数据存储在数据库中，

然后从 Web servlet 运行 Dijskra 算法，以使用存储的图形数据查找最短路径计算。然后我将打印来自 servlet 的 html 文件的路径。

问题是：假设我有一个sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)使用 BNF 指定的输入函数，我将使用递归下降算法解析输入，然后如何使用或更改 Dijkstra 的算法来处理这个给定的函数？我需要用罪来执行它 | COS | 平方 | ln，Dijkstra 的算法应该在其中完成工作。

编辑：也许我还应该问：表示给定功能的最佳实践或数据结构是什么？

编辑：输入集可以获取为：

编辑：Shunting Yard 是将输入函数转换为 RPN 的算法，但是如何扩展它以接受另一个函数，如 sin | COS | 平方 | 吗？递归下降是否为调车场提供了所需的扩展？

我最近问了一个关于 Dijkstra 算法之一的问题（分流场）。但几乎所有人都认为“Dijkstra 算法”是指他的最短路径算法。

Dijkstra 还开发了哪些其他算法？

我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道以前有人问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道你可以用什么软件来实现它。例如，如果它已经存在用于在无向图中执行 bfs 的库（带有 python 绑定！），那将是完全完美的。

此代码是我从算法设计手册书中构建的代码，但我无法编译它，因为我对指针的经验很少我认为这是我认为我无法编译它的主要原因：

如果有人可以在 djikstra 中进行一些更改，以使其通过当前配置的堆。

为什么我们不能将 Dijkstra 算法应用于具有负权重的图？

该图未加权，HashSets neighbours[] 数组的一个元素是节点 neighbours[1] 是节点 1（它们从 0 开始，请注意），其唯一的相邻节点为 2 3 4 5。（所以 neighbours[5]将包含 1)。我有以下方法，我做了很多帮助，因为我没有得到超出理论的算法。它返回的数字应该是图中 2 个节点之间的平均距离。

想象一下，我有以下图表（节点：in_links | out_links；neighbours[] 不包含节点 0 处的 0 循环，并且如我所说，没有重复。）

对于这个简单的图表，返回的距离是 5.781686749230769E8 ?!?! 编码：

我在铸造或打印实数方面没有太多经验，所以我希望这与这些有关！欢迎大家评论

问题是：考虑有 5 个顶点的有向图。让 Dijkstra 算法产生从节点 s 到所有其他节点的最短路径，如图 1 所示。让边 (x, t) 的权重增加并假设所有节点以某种方式获得此信息。node 如何修改 Dijkstra 的算法以使重新计算最少？以“节点 s 运行 Dijkstra 算法，将 S 初始化为并将列表（<每个节点>）维护为 ”的形式提供最终解决方案。</p>

我的问题是......这不是一个棘手的问题，因为它所做的只是增加从 s 到 t 的最短路径吗？

好吧，所以我的照片不工作

但它的工作原理是这样的：

s->y->x->t

y 也指向 z。y->z

这些是单向方向箭头。