问题标签 [floyd-warshall]

我正在编辑弗洛伊德的算法，所以不是每个 Dk，其中 k 是最高中间顶点，k 是最大路径长度。最终它将具有与 Floyd 相同的输出，但每个子迭代都可能不同。例如，如果有 4 个顶点：0、1、2、3，我想找到从 0 到 3 的最大长度为 K 的最便宜的路径。假设该图是有向的。

因此，如果 k=2，那么我只能检查 0->3...0->1->3...0->2->3，其中每个箭头都表示一条边/路径。如果 k=3，那么我只能检查 0->3...0->1->3...0->1->2->3...0->2->3... 0->2->1->3，等等……

除了弗洛伊德的算法，我需要帮助理解其中的实现，并且不知道从哪里开始。

我似乎无法找到一种方法来列出在我的算法（floyd-warshall）计算最短路径时传递的顶点。有人告诉我必须使用递归，但我不知道如何使用递归。请给出伪代码/示例，不胜感激！

如何沿着任意顶点之间的所有可能路径找到一组最小边权重的最大值(u,v)？

我在考虑修改 Floyd-Warshall？

最小边权重为 1

最小边权重为 3

因此结果是max(1, 3) = 3

Skiena 的算法书包含以下对Floyd Warshall 算法的解释：

Floyd-Warshall 全对最短路径在 O(n ³ ) 时间内运行，这在渐近上并不比对 Dijkstra 算法的 n 次调用更好。但是，循环非常紧凑，程序非常短，以至于它在实践中运行得更好。值得注意的是，它是一种罕见的图算法，它在邻接矩阵上比邻接列表工作得更好。

有人可以详细说明为什么粗体部分是真的吗？

关于

'a' 和代表什么以及 a 的两个维度中的每一个代表什么？

“n”代表什么？

我有一个位置列表，其中包含这些位置之间的连接列表，并计算了这些连接之间相互连接的距离。现在我需要找到任何给定两个位置（floyd's）之间的最短路径——但需要了解如何应用floyds(int a[][100],int n)到我的位置数组、城市词典和连接数组。

仅供参考 - 使用目标 C - iOS。

我正在尝试实现弗洛伊德算法。我认为我的代码有问题，我无法弄清楚。输出是不同的，它们只是缺少一些小东西。在我下面的代码中，我还包含了一个输入、输出和原始输出。我会很感激任何一点帮助。

*/

我实现了 Floyd-Warshall 算法。根据他们的矩阵，我可以得到正确的结果，关于两个地方之间的最短路径和它们的距离。我的问题是如何打印从 i 到 j 的最短距离。我做了一些研究，发现了一个这样的算法。谁能解释一下它应该如何，或者它是如何工作的，或者说任何其他建议？

我已经实现了 Floyd-Warshall 以返回每对节点/顶点之间的最短路径的距离以及每对节点/顶点之间的一条最短路径。

有没有办法让它返回每条最短路径，即使对于每对节点有多个最短路径绑定？（我只是想知道我是否在浪费时间尝试）

我一直在研究这三个，我在下面陈述我的推论。有人能告诉我我是否足够准确地理解它们吗？谢谢你。

1. Dijkstra 算法仅在您有单一来源并且您想知道从一个节点到另一个节点的最小路径时使用，但在这种情况下会失败

2. 当所有节点中的任何一个都可以成为源时，使用 Floyd-Warshall 算法，因此您希望从任何源节点到任何目标节点的最短距离。这仅在存在负循环时才会失败

（这是最重要的一个。我的意思是，这是我最不确定的一个：）

3.当只有一个来源时，Bellman-Ford 的使用与 Dijkstra 的一样。这可以处理负权重，它的工作方式与 Floyd-Warshall 的相同，除了一个来源，对吧？

如果你需要看一下，对应的算法是（由维基百科提供）：

贝尔曼福特：

迪杰斯特拉：

弗洛伊德-沃歇尔：

基本上，使用 Floyd-Warshall 算法的目的是确定连通图中两个节点之间的最短路径。我想要做的不是简单地找到最短路径，我想要的是最短路径，它也是一个均匀的重量。

例如，这是 Floyd-Warshall 算法的简单实现：

给定以下输入：

我想要以下输出（忽略格式，我只需要一种在每一步找到“奇数矩阵”的方法）

我的代码目前所做的是获得最佳权重，该权重在每个单独的“奇数”和“偶数”矩阵中表示。

我缺乏理解的是，当最优值位于相反矩阵（奇/偶）中时，“奇”和“偶”矩阵如何得出它们的非最优值。在我看来，必须有某种循环或递归才能做到这一点，但我不知道如何实现这一点。