问题标签 [dijkstra]

我正在尝试设计一个带有斐波那契堆的 dijkstras 实现。我想了解的是，除了 O(logn) 中的最小距离（带删除）之外，是否可以表示任何给定节点的邻居？或者这是否违反了斐波那契堆结构？否则我将不得不建立一个邻居列表以及一个斐波那契堆。

我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法。我知道 Dijkstra 找到了从一个节点到所有其他节点的最佳路线，而 Floyd-Warshall 找到了所有节点配对的最佳路线。

我的问题是，如果我在每个节点上运行 Dijkstra 的算法以找到所有配对之间的最佳路线，它会比 Floyd 的算法更有效。

Dijkstra 的运行时间为 O(E + VlogV)，其中 Floyd 的运行时间为 O(V ³ )。如果 Dijkstra 失败，在这种情况下它的运行时间是多少？谢谢！

我正在搜索长度为 12 的向量空间，条目为 0、1、2。例如，一个这样的向量是
001122001122。我有大约一千个好的向量和大约一千个坏向量。对于每个坏向量，我需要找到最接近的好向量。两个向量之间的距离只是不匹配的坐标数。好的向量排列得不是特别好，它们“好”的原因在这里似乎没有帮助。我的主要优先事项是算法要快。

如果我做一个简单的详尽搜索，我必须计算大约 1000*1000 的距离。这似乎很笨拙。

如果我首先使用好的向量应用 Dijkstra 算法，我可以计算空间中每个向量的最近向量和最小距离，因此每个坏向量都需要简单的查找。但是空间中有 3^12 = 531,441 个向量，因此预计算是一百万次距离计算。没有多少储蓄。

你能帮我想一个更好的方法吗？

编辑：因为人们认真地问是什么让他们“好”：每个向量代表六个等边三角形的六边形图片的描述，这是立方体 3D 排列的 2D 图像（想想广义 Q-bert）。等边三角形是立方体 (45-45-90) 面的一半，倾斜成透视图。其中六个坐标描述了三角形的性质（感知的地板、左墙、右墙），六个坐标描述了边的性质（感知的连续性，两种感知的不连续性）。1000 个好的向量是那些代表透视立方体时可以看到的六边形的向量。搜索的原因是对充满三角形的十六进制地图应用局部校正......

为什么贝尔曼福特算法允许负边缘循环，而迪杰斯特拉算法不允许负边缘循环？

对于大学的数据结构和算法课程，我们必须实现论文中提出的算法。论文可以在这里找到。所以我完全实现了算法，但仍然存在一些错误（但这并不是我问这个问题的真正原因，如果你想看看我到目前为止是如何实现的，你可以在这里找到它）

我在 Stackoverflow 上提问的真正原因是作业的第二部分：我们必须努力让算法变得更好。我想到了几种方法，但它们在理论上听起来都不错，但在实践中它们并不会真正做得很好：

• 在源节点和结束节点之间画一条线，搜索最靠近该线中间的节点，并将“路径”递归地划分为 2。如果单个 Dijkstra 进行计算，基本情况将是一个较小的图。这并不是对当前算法的真正调整，但有些人认为很明显这不会给出最佳解决方案。
• 尝试通过为指向末端节点的边赋予更高的优先级来给算法一些方向感。这也不会是最佳的..

所以现在我完全没有想法，希望这里有人能给我一点提示，以便可能进行调整。它实际上并不需要改进算法，我认为他们要求我们这样做的第一个原因是，我们不只是在不知道其背后是什么的情况下实现论文中的算法。

（如果 Stackoverflow 不适合问这个问题，我很抱歉 :)）

算法的简短描述：算法尝试选择哪些节点看起来很有希望。通过承诺，我的意思是他们很有可能躺在最短的路径上。一个节点的前景如何由它的“范围”表示。路径上顶点的范围是它到起点和终点的距离中的最小值。图中一个顶点的范围是该顶点在所有最短路径上的最大范围。为了最终确定一个节点是否被添加到 Dijkstra 算法中的优先级队列中，添加了一个 test() 函数。

危害德怪异

存在哪些与 Dijkstra 概念不同的路由算法？

Dijkstra（和 A*、D*、bellman forge 等）使用这个概念：从已知节点中获取最佳节点，展开并将结果保存到已知节点。

有没有根本不同的概念？

所以我想这对于在 CS 中拥有 MSC 的人来说是一个经典问题。

我有 N 个元素，我也有距离。假设我有 3 个具有以下距离的元素。它是对称的，所以

它看起来像一个矩阵：

我的问题是：

• 我怎样才能有效地存储它（什么数据结构）
• 获得距离总和最小的链表的最有效方法是什么

在这种情况下，最好的是

其他情况：

我的印象是 BFS 可能适合这个。英文文档的链接很好，即使是亚马逊上的书籍......

如果我们去特定的顶点，我们如何使用 Dijkstra 或 Bellman-Ford 的算法来找到图中某些边会受到影响的最短路径。这样，受影响边缘的长度将大于或小于原始长度。

我在下面有这个 Dijkstra 算法 java 代码。我下载了代码。我想对该程序进行更改并将数据存储在文件中并将其读入而不是将其放入源代码中。最好的方法是什么？

该代码基于http://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29 [最后访问时间：2011 年 1 月 6 日]

我想从简单的图形格式 txt 文件创建对象、顶点和边。这里的一位程序员建议我使用简单的图形格式来存储 dijkstra 算法的数据。

问题是目前所有的信息，例如重量，链接，都在源代码中。我想为此创建一个单独的文本文件并将其读入程序。

我考虑过使用扫描仪使用代码来扫描文本文件。但我不太确定如何从同一个文件创建不同的对象。请问我可以帮忙吗？

该文件是

而dijkstra算法代码是

下载自：http ://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29 */

扫描文件的代码是