问题标签 [floyd-warshall]

我正在查看一些旧的竞赛问题，我发现了这个，它看起来很有趣，http ://dwite.ca/old/Problem5Jan2006.pdf，我尝试使用 floyd warshall 算法来获得从任何节点到任何节点的最短路径其他节点，你们能看到我做错了什么吗？它没有给出竞赛问题页面上列出的所需输出

我已经实现了 Floyd Warshall 算法并且它可以工作，但问题是我不知道如何找到所有未定义的路径。我在网上搜索过，但我只能找到如何检测图表是否有负循环的答案。

在图上运行算法后：

我得到邻接矩阵：

我知道如果节点 i 是负循环的一部分，它在矩阵中的位置 d[i][i] 处具有负值。因此，如果我检查矩阵的对角线，我可以找到属于负循环的所有节点。因此，如果我们查看上面的示例，我们可以看到节点 1 和 2 是负循环的一部分。问题是我想找出哪些路径已定义，哪些未定义。如果您可以通过负循环从 A 到 B，那么路径的长度应该是未定义的，因为它可以任意小。

所以问题是，我怎样才能找到所有未定义的路径？

我希望算法返回矩阵：（而不是上面的那个）

其中 d[i][j] = INF 表示 i 和 j 之间没有 Path，-INF 表示 i 和 j 之间存在任意小路径（路径在某处经过负循环），否则为 d[i ][j] i 和 j 之间的最短长度。

我正在考虑测试每条路径，但这可能太慢了。必须有一些标准的方法来解决这个问题，对吧？

谢谢

由于 Floyd-Warshall 算法是动态的，这意味着它必须始终提供最佳解决方案，对吗？所以让我感到困惑的是，在算法的每个部分中，这些最佳解决方案的性质是什么——特别是，我试图理解以下三个问题：

• 迭代 0：在任何迭代发生之前提供什么最佳（即精确）解决方案 ？

• 迭代 1：在本次迭代结束时提供什么最佳（即精确）解决方案？

• 迭代 i（对于任意 i > 0）：在此迭代结束时提供什么最佳（即精确）解决方案？

任何人都可以阐明这些担忧吗？

我正在使用 Floyd-Warshalls 算法进行图形搜索，但不明白如何改变它以防止负循环。

当我输入：

我得到成本矩阵：

然后它开始循环直到它崩溃，因为它仍然增加负边缘并进一步降低成本。

其中 min 是：

我的 distanceMatrix 有 INF，只要没有成本。

我遇到了较旧的主题，其中更改后的算法是这样的：

但是，即使我使用此修复程序而不是我的函数，它仍然会循环并进一步降低成本。这个修复正确吗？如果没有，我应该如何重写它？谢谢。

我知道检查加权有向图的给定边是否属于负循环的问题是 NP 完全的（找到包含所有负循环的最小子图）并且 Bellman-Ford 允许在 O( |V|*|E|) 时间。但是如果我想找到所有属于负循环的顶点呢？我想知道它是否可以比 Floyd-Warshall 的 O(|V|^3) 更快。

我使用矩阵d来呈现图表。表示和d.(i).(j)之间的距离；表示图中的节点数。ijv

该图中可能存在负循环。

我想检查是否存在负循环。我从Floyd-Warshall的变体中写了如下内容：

我的问题是

1. 上面的代码正确吗？
2. part 1有用吗？

因为我经常调用这个函数，所以我真的想让它尽可能快。所以我的 3) 问题是其他算法（尤其是Bellman-Ford）是否可以比这更快？

我在看Floyd-Warshall 算法。

在页面中，它说the Floyd–Warshall algorithm assumes that there are no negative cycles。所以我的问题是如果入口图隐藏了负圆会发生什么。输出会dist代表另一个隐藏负圆的图吗？这不part 1无效吗？

我正在尝试实现 Warshall 的算法来快速计算 LR(1) 闭包。

我想我了解它对 LR(0) 的工作原理：

• 图的节点是LR 项，例如A → B • C
• 边缘是从A → B • C到的“过渡”C → • D

问题是，LR(1) 需要计算前瞻，我不知道如何将它们合并到算法中。
在我看来，即使我知道任何给定 LR 项目的传递闭包，我仍然需要通过所有相同的计算来确定每个项目的前瞻集是什么。

甚至可以使用 Warshall 的算法来计算规范的 LR(1) 闭包，还是仅适用于更受限制的情况（如 LR(0)、SLR(1) 等）？

我在 MySQL 存储过程中实现了 Warshall 算法。不幸的是，该过程需要很长时间才能完成。我是编写存储过程的初学者，你知道我能做些什么来让它更快吗？

简要说明：我正在尝试计算邻接表的传递闭包。我想知道，连接了哪些节点（直接在一条边上，或间接在更多边上）。例如：

下图说明了图表：

_{图片来自维基共享资源： https ://en.wikipedia.org/wiki/File:Transitive-closure.svg}

您可以在SQL Fiddle或此处查看代码：

在我的计算机上运行具有 1466 条记录的表需要 45 秒：

我需要一个高效的 SPARQL APSP 实现。我目前有一个由 py​​thon 驱动的 Floyd-Warshall 工作，但它在最内层循环的每次迭代中都使用更新。为了遍历节点，我将所有节点放在一个列表中，删除并单独处理每个节点。哎哟。不幸的是，Floyd-Warshall 似乎需要这种单独的节点处理。有谁知道更好的 APSP，或者更好的方法来做我所做的事情？代码如下。谢谢。