问题标签 [floyd-warshall]

我有一个加权 DAG，带有一些负边权重，并且想在其中找到所有最短路径。有没有比 O(n^2) 复杂度更好的算法。（我的图是完整的，即对于 {1..n} 中的任何 i,j 和 i < j 都有一条边 (i,j)。

谢谢

可能重复：
安卓锁密码组合

尊敬的先生，我遇到了一个问题，该问题要求在给定 3x3 矩阵的情况下找到所有可能的唯一模式，其中的数字为 1-9。这与android锁屏相同。你能帮我怎么找到它吗？？我在想我们可以为此使用弗洛伊德战争并在后续矩阵中的值发生变化时增加计数吗？

我已经尝试了一周来为我正在开发的游戏寻找路径。我正在使用Floyd Warshall 算法的这个实现。我相信我已经设法将问题缩小到这个循环中：

我一直在用 4 个节点进行测试，每个节点都连接到所有其他节点，并且所有连接的权重为 1。这是循环之前所有相关变量的值。

输出：

这和预期的一样

输出：

这也符合预期。

输出：

这也符合预期。

输出：

这就是我认为问题所在，我希望输出包含所有不同的节点，只有在这里找到的两个节点在 getShortestPath 函数中工作。我相信这将是循环的正确输出，据我所知，顺序应该是无关紧要的。

我不知道究竟是什么导致了循环中的问题，或者我是否对算法有误解。

对于 Floyd-Warshall 算法，循环的顺序是 k、i 和 j。如果我把循环的顺序搞砸了，不小心把它写成 i、k 和 j，会发生什么？该程序以何种方式不起作用？谢谢！

对于一个作业，我被要求找到一种算法，该算法使用 O(n 4 ) 时间计算有向图的传递闭包。我们已经了解了 floyd warshall 算法，它要好得多，所以有人可以帮我创建一个在 O(n4) 时间内运行的算法吗？有这样的算法吗？

我知道这似乎是一个愚蠢的问题。我真的不明白为什么我们被要求找到更慢的方法来做到这一点。

我正在尝试使用弗洛伊德的算法来生成一个通过具有 98 个航点（位于每个迷宫顶点）的迷宫的最快路线矩阵。当算法运行时，它会填充两个矩阵 - 距离矩阵（两个节点之间的最佳距离）和路径矩阵（下一个节点要转到任意两个节点之间的最佳路径）。

距离矩阵使用我在之前代码中生成的邻接矩阵进行初始化。我还生成了一个数据结构，其中包含指向每个航路点的四个可能的相邻航路点的指针，但我没有在生成路径矩阵时使用此数据结构。

这是我的 C# 代码：

我相信我计算路径矩阵不正确，因为使用此代码生成的路径矩阵的机器人在大多数情况下都失败了（因为路径矩阵告诉要穿过墙等）。

我已经盯着这段代码看了好几个小时，我对自己做错了什么感到困惑。如何生成正确的路径矩阵以用于我的迷宫导航代码？

是否有一个简单的解释来解释为什么这个片段找到两个顶点之间的最短距离

而这并没有

（因为 k 是第二个片段中最里面的一个）

我已经阅读并搜索了 Floyd Warshall 算法，我想我理解它。但是在我在“算法简介（Thomas H. Cormen 的书）”一书中读到的示例中，我堆叠在一个点上。我很困惑。这是书中相同的图片。我的问题在最后一步，即 π(5)。这是示例：http: //integrator-crimea.com/images/fig653_01_0.jpg

有人可以解决我上面的困惑吗？书上写错了吗？

我正在尝试在 C++ 中实现 Floryd 算法

我已经有了这个：

a 表示边缘开始的节点。

b 表示边结束的节点。

t 表示边缘的时间。

m 表示边数。

n 表示节点数。

当我尝试代码时，程序崩溃说：“表达式：向量下标超出范围”

我希望你们能帮助我，因为我无法解决这个问题！

我正在实施Floyd-Warshall 算法。

我有大约 50 个节点的完整图，我想找到所有节点之间的最大路径。算法返回的路径可以是任何长度 1< x<50，我需要这个长度最多为 3-4 条边长，我该如何更改算法呢？