问题标签 [dijkstra]

我有兴趣找到图中任何节点与根/源之间的最小距离。所有链接都有权重。我不认为我需要使用previous[]，在维基百科文章中指出，因为我不需要知道每个节点的父节点。那是对的吗？此外，如果权重都等于 1，我想我可以运行 BFS？

我有一个脚本，其中放置了 803*803 (644 809)图表，每个图表中有 1 000 000 个值。使用 ~500*500 一切正常 - 但现在它崩溃了 - 它试图分配超过 64MB 的内存（我没有）。解决方案是什么？以某种方式“拆分”它还是...？

*这是关于 Dijkstra 算法的

ps 不，我不能分配超过 64MB

上述算法已在 Wikipedia 中提到了 Dijkstra 最短路径。我在这里无法理解的是，虽然我们将所有顶点的距离设置为无穷大[第 3 行]，但在第 9 行我们正在分配u := vertex in Q with smallest dist[]，但由于所有距离都是无限的（如第 3 行中设置的那样）怎么可能有最小的距离？

我需要在 Python 中实现 Dijkstra 算法。但是，我必须使用 2D 数组来保存三条信息——前任、长度和未访问/已访问。我知道在 C 中可以使用 Struct，虽然我被困在如何在 Python 中做类似的事情，我被告知这是可能的，但我不知道说实话

Dijkstra 算法在寻找最短路径方面如何优于 A* 算法？

我正在尝试编写 Dijkstra 的算法，但是我正在努力解决如何在代码中“说”某些事情。为了形象化，这里是我想用数组表示的列：

因此，将有几个数组，如下面的代码所示：

粗体部分是我坚持的地方 - 我正在尝试实现算法的这一部分：

3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。例如，如果当前节点 (A) 的距离为 6，并且连接它与另一个节点 (B) 的边为 2，则通过 A 到 B 的距离将为 6+2=8。如果此距离小于先前记录的距离，则覆盖距离
4。当我们考虑完当前节点的所有邻居后，将其标记为已访问。被访问的节点将不再被检查；它现在记录的距离是最终的和最小的

我想我在正确的轨道上，我只是坚持如何说'从一个节点开始，获取从源到节点的长度，如果长度更小，覆盖以前的值，然后移动到下一个节点

我有以下带有 3 个输入变量（开始、停止和时间）的Dijkstra 算法。大约需要0.5-1s才能完成。我的托管服务提供商说它使用了太多资源，我应该实现一些缓存机制。我的问题是，怎么做？

因为我有 3 个变量，如果其中只有一个发生变化 - 整个结果是不同的（因为我有一些关于时间的附加语句，没关系）。那么如何实现一些缓存机制或者做一些优化呢？

我有1700 个节点。

我遇到了一个我不知道如何解决涉及 Dijkstra 算法的问题 - 这是我的代码：

当我运行此代码时，我收到以下错误：

我不确定如何纠正这个错误（asterix 之间的部分） - 我要做的是读取我的文本文件，它只是一系列用逗号分隔的整数，并计算该文本文件中的节点数然后将为每个节点分配 Node 类中的值

罗文先生计划徒步游览巴黎。不过，由于他有点懒惰，所以他想走最短的路径，穿过他想去的所有地方。他计划从第一个地方坐公共汽车，从最后一个地方再坐一辆，所以他可以自由选择起点和终点。你能帮助他吗？

输入

输入的第一行包含访问地点的数量 (n)。然后，在接下来的 n 行中，您找到每个要访问的地方的坐标。这是一个例子：

3

132 73

49 86

72 111

输出

对于每个测试用例，假设从一个地方到另一个地方的步行距离是欧几里得距离，您的程序应该输出一行，其中包含 Rowan 先生访问所有地方必须步行的最短距离。该算法应该以定点表示法输出一个数字，小数点右侧恰好有 3 位数字，并且没有前导空格。最多有12个地方可以参观。例子

示例输入：

3

132 73

49 86

72 111

示例输出：

104.992

我一直在为我的家庭作业编写这段代码，但我无法让它工作，我开始想知道这是否是最好的方法..

问题是 floyd-warshall 函数，它对 float **path 结构没有任何作用.. 不知道为什么.. 在 floydwarshall(path, n, next) 之前和之后路径是相同的；

我开始开发一个 Web 应用程序，该应用程序将利用 Dijkstra 的算法为用户找到从 A 点到 B 点的最快方向。我只是想知道是否有人对此框架有任何建议？我倾向于涉及 PHP 的东西，但我真的不想构建我自己的框架，因为这似乎有点矫枉过正。

我只得到了一些可以使用的图像，有人对我如何从 A 点到 B 点画一条线有建议吗？