问题标签 [floyd-warshall]

我正在尝试从我在 Lua 中实现的 Floyd-Warshall 算法重建两个顶点之间的成本最低的路径。

这是我到目前为止所写的：

这些函数为我提供了一个矩阵，其中包含分隔图 g 中每对顶点的长度（边数），这很棒。

我现在需要知道任何给定顶点之间的实际路径。维基百科方便地提供了伪代码，但是——作为一个新手——我对如何实现它感到困惑。

这是维基百科文章中提供的伪代码（https://en.wikipedia.org/wiki/Floyd –Warshall_algorithm#Path_reconstruction）：

有人知道如何在lua中实现这个伪代码吗？我是否需要重新编写我的一小段 lua 代码，或者这个伪代码可以以某种方式合并到我所拥有的中？

干杯!

是否可以为 APSP 问题热启动任何众所周知的算法（Dijkstra/Floyd-Warshall 等），以便能够降低时间复杂度，并可能降低计算时间？

假设该图由 NxN 矩阵表示。我只考虑一个或多个矩阵条目（<< N）的变化，即相应顶点之间的距离，在对算法过程的任意 2 次调用之间。我们可以使用第一次调用的解决方案和矩阵的增量更改来加速第二次调用算法的计算吗？我主要看密集矩阵，但如果有已知的稀疏矩阵方法，请随时分享。谢谢。

“让 G 是一个没有负循环的有向加权图。设计一种算法来找到 G 中以 O(|V|^3) 的时间复杂度运行的最小权重循环。”

以上是我在课程作业中一直在研究的一个问题。当我第一次阅读它时，我立即认为 Floyd-Warshall 算法可以解决这个问题——主要是因为 FW 运行时间为 O(|V|^3)，它适用于没有负循环的正负加权图。但是，我很快就记起 FW 旨在找到图的最短路径，而不是最小权重循环。

我在这个问题上是否正确？是否可以修改 Floyd-Warshall 算法以在图中找到最小权重循环？

我试图通过计算所有对之间的最短路径来使用 Floyd-Warshall 算法找到源和目标之间的最短路径。

我需要找到最短的路径，而不仅仅是距离。这就是我想要做的：
我将第一个顶点存储在从 i 到 j 的最短路径上。每当从 i 到 j 的最短路径更新并且它现在经过 k 时，我将从 i 到 j 的最短路径上的第一个顶点设置为从 i 到 k 的最短路径上的第一个顶点。

这个算法的问题是，当我在下图上运行这个算法时，这个算法找到的路径是一个无限循环。

这是first算法计算的矩阵：

根据算法，从 0 到任何其他顶点的最短路径上的第一个顶点是 4，但从 4 到任何其他顶点的最短路径上的第一个顶点是 0。

• 为什么该算法会以这种方式运行？
• 当我计算路径的长度时，是否有另一种方法来计算每条路径上的第一个（在源之后）顶点？

我已经阅读了维基百科的文章以及一些关于 SO 的问题，但它们并没有太大帮助。

我有一个学校项目，我必须使用 Floyd Warshall 和 Dijkstra 算法找到两个节点之间可用的最短路径。一切都很好，但是除此之外，我必须对两种算法进行修改，以便计算多个任务的最佳路线。

该场景基于公共交通接送服务。例如：你会有一个人想从 C 到 B，另一个从 D 到 B，也许还有另一个从 C 到 F。

这个概念是始终从节点 A 开始，并计算满足所有请求的最佳路线。

任何人都知道正确的方向来解决这个问题？

基本上，我的任务是实现 Floyd 算法来找到矩阵的最短路径。在我的例子中，一个值 arg 被输入，矩阵变成大小 arg*arg。下一串值按接收顺序应用于矩阵。最后，a -1 代表无穷大。

老实说，我不知道我的问题出在哪里。通过测试时，第一对通过了，但其余的都失败了。我只会发布前两次失败以及通行证。我只会发布相关的代码段。

这是我收到的失败。其余的变得越来越长，最多为 20*20 矩阵，所以我将不再赘述：

如果有人向我展示使用 Floyd 和 Warshall 等动态编程算法计算最小路径的方法，我将不胜感激。该算法必须在每次交互时计算路径，它必须在考虑节点的情况下决定选择哪些节点已经穿越了。

我做了一点解释： https ://drive.google.com/file/d/0B3i9KFQXzB89YXl0VkEzaDZDMHc/edit?usp=sharing

我的图表存储在 neo4j 环境中，它可以以严重的方式增加他的维度。我将 rest 与每个人的 php neo4j 库一起使用。做这个的最好方式是什么？遍历，密码，gremilins，从http://components.neo4j.org/neo4j-graph-algo/1.4/xref/org/neo4j/graphalgo/impl/shortestpath/FloydWarshall.html开始编写自定义算法？

提前 Tnx

在解决具有n 个节点的有向加权图的最短路径问题时，是否可以修改 Floyd-Warshall 算法，使得每条最短路径的步数不超过m？更准确地说，对于每对节点i和j，您将找到从i到j的最短有向路径，其中包含不超过m个节点。时间复杂度仍然保持O ( n ³ ) 吗？

使用 Floyd-Warshall 的算法来查找两个顶点之间的最短路径，在 Java 中实现时我应该如何表示无穷大？我在这里使用无穷大来表示两个顶点之间没有路径。

谢谢

我创建了这个算法来获得地图上两个选定点之间的最短点。

首先，我用距离、重量完全填充了矩阵。我命名它，例如：dist[0,1] 指的是点 0 和点 1 之间的道路。每个点都有一个分配给它的数字。

矩阵都相应地填充，然后 Fjord Warshall 算法运行：

这得出了每条路径之间的最短点。然后我检查我拥有的路径以获得它的最短点：

哪个返回正确的值，一切正常。这是我的问题。我需要将其设置为查看它通过哪些点。我的意思是，如果我想从点 1 到点 5，并且最短的路线是通过 3 和 6，它将显示 1、3、6、5。

有任何想法吗？完全卡在了这个上。