问题标签 [floyd-warshall]

假设给定一个加权有向图G = ( V , E )，其中有n 个节点，其中p是中心节点。让C , | C | = p 是中心节点的集合，N = V \ C是非中心节点的集合。边e _ij的值是有限非负实数，如果：

1. i来自集合N，而j来自集合P，或
2. i来自集合P，而j来自集合P，或者
3. i来自集合P，而j来自集合N。

否则，如果i来自集合N并且j来自集合N，则e _ij的值等于正无穷大。

我们有兴趣在图G中找到所有最短距离的最大值。我发现解决这个问题的最快算法是使用对 Floyd-Warshall 算法的简单修改，该算法在O ( n ² p ) 中运行。这是简单的伪代码：

可能没有比这更快的算法了。（或者，我错了吗？:)）

但是，我对以下内容更感兴趣，我认为这里有更快的东西。假设我们只是从集合C和N中交换两个节点，即。对于来自C的一些v _c和来自N的一些v _n，集合C变为C + v _n - v _c并且集合N变为N + v _c - v _n。现在，我们感兴趣的是在G中的所有最短距离上找到新的最大距离。

我知道的更快的算法是简单地使用描述的 Floyd-Warshall 方法从一开始计算新的最大距离，该方法在O ( n ² p ) 中再次运行。有没有更快的计算方法，可能在交换节点之前使用最短距离的旧计算值？

是否可以使用邻接列表对 Floyd Warshall 进行编码？我必须处理来自文本文件的一百万个顶点，因此，邻接矩阵不是解决方案。任何实现已经可用？请帮忙。

我试图在无环有向图中找到所有节点对之间的最长路径。我的问题是，如果我在邻接矩阵中做出以下初始条件，Floyyd Warshall 会给出正确答案吗？

1. 如果 i=j，Adj[i][j]=0
2. Adj[i][j]=-1*INF if i!=j 并且节点 i 和 j 之间没有边
3. Adj[i][j]=w[i][j] 否则，其中 w[i][j] 是节点 i 和 j 之间边的权重

边的权重可以是正的也可以是负的。

例如，

比方说

所以1->2->4成本700

如果从 4 到 3 的优势是 -500 怎么办？以及从 3 到 4 的不同优势，花费 200

所以1->2->4->3->4成本400

小于700

所以被1->2->4->3->4认为是比1->2->4???更短的路径

我知道不允许循环，这是一个没有重复边缘的路径示例。

顶点呢？如果他们重复，这是弗洛伊德沃赫萨尔允许的循环吗？

因为我知道有不同类型的算法，一种允许一种循环而不允许其他类型的循环。

谁可以给我解释一下这个？回答问题，被1->2->4->3->4认为是比1->2->4???更短的路径

谢谢大家。

编辑：

这是一张图片，显示您不必两次访问同一边缘。

我为每个节点获得-0.00000输出。

PS 我在 CL_DEVICE_TYPE_CPU 上运行我的代码，因为在 GPU 上它给出了无法获取设备 ID 的错误。

请就如何获得正确的输出提供一些指导。

我实际上是在尝试实现弗洛伊德的 warshall 算法，但我遇到了一个难点。当我试图在我的序列矩阵中找到最短路径时，我遇到了分段错误。我遵循本教程： 弗洛伊德的战争算法

除了第 124 行，一切都运行良好：

我在哪里得到段错误（你可以跳过第一部分，除非你想知道我如何实现算法，但问题在第二部分）：

感谢您的关注和花时间帮助我！

我正在实施弗洛伊德 Warshall 算法。我将此算法应用于具有不同顶点的图，其中一些没有链接。我的代码没有得到正确的答案。

从一个顶点到另一个顶点生成的最终路径有时包括一条不存在的边。我认为我的错误来自我将无穷大与无穷大进行比较的事实。我目前这样做：我假设一个大整数将代表无穷大，例如 10000。当我遇到像 10000 > 10000 + n 这样的情况时我应该怎么做？n < 10000

如何修改 Floyd-Warshall 算法以找到保持 O(V^3) 时间复杂度的有向图的任何负成本循环的最短路径？

我不断收到这个关键错误，我不明白怎么做。我正在使用 for-in 语句，因此密钥肯定存在：

错误：

关键错误只是在节点中首先出现的任何键上，每次都会更改

一只青蛙想过河。

河里有3块石头她可以跳过去。

她想在所有可能的路径中选择导致最小最长跳跃的路径。

IE。每条可能的路径都会有一个最长的跳跃。她需要找到最长跳跃最小的路径。

2 个海岸相距 10 并且平行于 y 轴。

每个石头位置由 x 位置的列表 x=[x1,x2,x3] 和 y 位置的列表 y=[y1,y2,y3] 给出。

通过路径中石头列表 x 和 y 中的索引列表返回此路径中最长的跳跃（四舍五入到最接近的整数）和路径本身。

这是我找到最长跳跃的python代码。

我将如何跟踪路径本身？

而且我的代码看起来很笨拙，有 3 个嵌套循环有没有更好/更优雅的方式来编写这段代码？