问题标签 [floyd-warshall]

我很难理解Floyd-Warshall 算法。我知道它是如何工作的，就像我知道如何用手做一样，但我需要通过计算机感知来理解它。

k, iandj是迭代的变量，它迭代直到n值，我猜它是一个嵌套循环，然后它查看每个节点，然后找到最短路径？

我正在尝试在迷宫上实现 Floyd-Warshall 算法来计算从一个点到迷宫内所有其他点的距离。出于某种原因，当我使用k等于列和行之间最大值的 a 时，我得到的答案不正确。

k有没有办法用一个对于给定迷宫的所有长度都正确的值来解决这个问题？

换句话说，有没有办法将 Floyd-Warshall 算法用于非 n×n 矩阵？也就是说，对于 am×n 矩阵 where m!= n?

我需要通过一个无向图找到一条最短路径，该图的节点是实数（正负）加权。这些权重就像您可以通过进入节点获得或失去的资源。

路径的总成本（资源总和）不是很重要，但它必须大于 0，并且长度必须尽可能短。

例如考虑如下图：

最短路径是 AEFED

Dijkstra 的算法本身并不能解决问题，因为它不能处理负值。所以，我想到了几个解决方案：

第一个使用 Dijkstra 算法计算从每个节点到出口节点的最短路径的长度，而不考虑权重。这可以像 A* 中的某种启发式值一样使用。我不确定这个解决方案是否可行，而且成本很高。我也想过实现 Floyd–Warshall 的算法，但我不确定如何实现。

另一种解决方案是不考虑权重，用Dijkstra算法计算最短路径，如果计算出路径的资源总和小于零，则通过每个节点找到一个可以快速增加资源总和的相邻节点，并将其添加到路径（如果需要，可以多次）。如果存在足以增加资源总和但距离计算出的最短路径较远的节点，则此解决方案将不起作用。

例如：

你能帮我解决这个问题吗？

编辑：如果在计算最短路径时，您到达资源总和为零的点，则该路径无效，因为如果没有更多汽油，您将无法继续。

我已经实现了 Floyd-Warshall-Algorithm 来解决 All-pairs 最短路径问题。现在我发现我也可以通过简单的修改来计算极小极大或极大极小路径。但我不明白结果是什么意思（什么是极小极大路径）。我在网上找到了一些解释，但它们让我感到困惑。

Minimax - 图问题中的 Minimax 涉及找到两个节点之间的路径，该路径使沿路径的最大成本最小化。

Maximin - 与 Minimax 的相反方式 - 在这里您遇到问题，您需要找到最大化沿路径的最小成本的路径。

有人可以尝试给出其他解释或示例吗？

我正在研究一个深入研究的问题：

有一个连通的无向图。我需要访问所有节点而不多次访问节点。我可以在任意节点开始和结束。

我该怎么办？我应该将算法Floyd-Warshall应用于所有可能的起始节点还是有更好的方法？

谢谢。

我目前正在使用 Java 开发一个小型的塔防项目，但我被寻路所困。我读了很多关于 A* dijkstra 之类的东西，但我认为使用 Floyd-Warshall 进行寻路可能是最好的（至少在我看来，它解决了所有对最短路径问题）。

无论如何，我试图自己实现它，但它并不能完全按应有的方式工作。我使用维基百科上的代码作为开始http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

所以这是我的代码：

}

Floyd-Warshall 算法设计用于处理图，因此我创建了一个图，其中每个节点都知道其邻居（即它所连接的节点）。

实际上，我现在不知道哪里出了问题，但不知何故。但至少看起来邻接矩阵的初始化是有效的。

在 floydwarshall 函数中，我希望在 next[][] 中获取下一个节点的索引，但我只得到 null 或 10/11；

所以我的问题是我做错了什么还是我的方法完全错误？我希望有一个人可以帮助我。如果您需要任何进一步的信息，请询问

PS对不起我的英语不好;）

我正在尝试查找 5x5 矩阵的所有对最短路径矩阵，但输出未显示正确答案。

这是初始矩阵和我的输出：

这是实际的解决方案：

如您所见，它正确读取了初始矩阵，但在代码中的某处，数学没有被正确应用，或者有些东西搞砸了。

下面是我的代码，你能找到我的错误吗？

给定一个有向无权无环图，我正在尝试调整 Floyd-Warshall 算法来计算 2 个顶点之间的路径数。我的代码目前如下所示：

对于 1 到 n 中的所有 k 对于 1 到 n 中的所有 i 对于 1 到 n 中的所有 j Aij = Aij + ( Aik * Akij)。

因此，我没有检查和替换最小距离，而是执行以下操作：

( i, j) 之间不带k+ 的路径计数（从i到的路径计数 * 从*k开始的路径计数）kj

我的最终数组应该有任意 2 个顶点之间的路径数。

我无法证明这并没有给我 2 个顶点之间的简单路径的计数，但是没有建议在其他地方使用这种方法。

有人可以提供一个失败的反例吗？

PS：这不是我的作业，只是我捡到的一个编程练习。

几天来，我一直试图弄清楚如何实现弗洛伊德算法，以找到网格结构中的最短路径，如下所述。谁能指出我将如何实现这样的事情的正确方向？谢谢。

输入：

• 开始/结束坐标
• 用户输入必须介于 0 到 10（含）之间
• 障碍物数量
• 左上角和右下角的障碍物坐标

输出：

• 显示通过的所有坐标的路径
• 距离作为整数

限制：

• 障碍物不能重叠
• 不能在矩形障碍物内设置开始和结束
• 路径可以包括沿着矩形的边缘行进，但从不穿过它们
• 路径只能水平和垂直，而不是对角线
• 两个相邻顶点之间的距离为1

我需要帮助生成 121x121 数组的条件。

这就是我到目前为止所拥有的。

两个简单的问题，我的大脑不工作了。我正在使用弗洛伊德算法并尝试重建从顶点 U 到顶点 V 的路径。这是我重建路径的代码。

举个例子，让 u = 0 和 v = 3，并让从 0 到 3 的最短路径为 0,1,2,3。但是我有两个问题。我的 pathList 是该类的实例变量，并且：

1. 我希望列表返回“0,1,2,3”，但它只返回“0,1,2”，或者如果我用 pathList.add(v) 替换 pathList.add(u)，那么它只返回“ 1,2,3" 我不知道如何让它返回整个路径，包括两个末端顶点。尝试放置 pathList.add(other vertex) 将导致它复制每个中间顶点。
2. 当我再次调用该方法时，让 u = 3 和 v = 0，并让从 3 到 0 的最短路径为“3,0”（已经是最短路径），它只是添加到我之前的列表中，导致我的错误从上面的 “0,1,2,3”或“1,2,3,0”当它应该只是“3,0”时

有什么帮助吗？