问题标签 [floyd-warshall]

我正在尝试解决以下问题：

在我们的银河系中有 N 颗行星。您可以在不同的行星之间旅行，但并非每个行星都通过安全路线与另一个行星相连。每条路线都有给定的光年长度。你的任务是在一组给定的行星 T（其中 0

输入由 N（行星数量）、R（行星之间安全路线数量）、R 路线组成，形式为三元组 ABL，其中 A 和 B 表示行星的恒星 ID，L 表示它们之间的距离年，T（需要建立基地的行星数量），后面是T数字，代表需要建立基地的行星的ID。

您总是从 ID 为 0 的行星开始。在行星 0 上建立基地可能需要也可能不需要。

我尝试解决这个练习并设法得到一个可行的解决方案，但它太慢了。我使用 Floyd Warshall 算法来获得图中任意两个节点（行星）之间的最小路径。接下来，我找到需要以 0 为基数的最近行星，并计算该路径。然后，我将此行星添加到“访问过的行星”列表中，并将其从“目标”行星列表中删除。我重复这个过程直到最后，但现在我试图找到从目标行星到我访问过的任何行星的最近的行星（因为在它们之间旅行是免费的，我不在乎我最后一次去了哪里）。然后，我添加距离，将其从目标中移除，将其添加到已访问并继续前进，直到建立所有必要的基础。

这提供了正确的输出，但它太慢了。

有什么改进的想法吗？可能是 Dijkstra 算法的一些修改版本？

我发现了以下内容：

给定一个有向图，找出给定图中所有顶点对 (i, j) 的顶点 j 是否可以从另一个顶点 i 到达。

这里可达意味着有一条从顶点 i 到 j 的路径。

可达性矩阵称为图的传递闭包。

该图以邻接矩阵的形式给出，例如 'graph[V][V]' 其中如果从顶点 i 到顶点 j 有一条边，或者 i 等于 j，则 graph[i][j] 为 1，否则为图[i][j] 为 0。

我们可以使用 Floyd Warshall 计算距离矩阵 dist[V][V]，如果 dist[i][j] 是无限的，则 j 不可从 i 到达，否则 j 可达且 dist[i][j] 的值将小于 V。

首先，你能解释一下为什么函数的参数是 graph[][V] 而不是 graph[V][V] 吗？

那我们为什么要初始化矩阵，它最终将在每对顶点之间具有最短距离，用graph[V][V]？

你能解释一下初始化后在for循环中做了什么吗？

我们怎么能写这个命令：reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);elsewhise？

编辑：图是布尔矩阵，还是不是？

如果是这样，那么到达不是一个布尔矩阵吗？

所以如果我们有这个命令： (reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); ) 并且如果reach[i] [j]=1 然后我们执行这个：reach[i][j]=reach[i][j]，否则我们检查 (reach[i][k] +reach[k][j]) 是否为非-零？

还是我理解错了？

要为 Floyd Warshall 算法“最短路径”（https://www.cs.usfca.edu/~galles/visualization/Floyd.html?hc_location=ufi）制作距离矩阵，您需要一些道路作为顶点和之间的距离这些道路作为边缘。例如（出发地、目的地、距离）：roads = [["Philadelphia", "New York City", 120 ], ["New York City", "Philadelphia", 97 ],[ "Millburn, "New York City", 25 ],["Morristown", "Harrisburg", 150] 如何在 python 中制作这个矩阵？

这是结构：

我不知道如何在正确的位置填充距离，因为network[roads[i][0],[roads[i][1]]当目的地或出发地被多次使用时，这不是正确的解决方案。

非常感谢！

我阅读了 floyd warshall 算法的伪代码， 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if 但它只使用一个 dist 矩阵来节省距离。我认为应该有 n 个 dist 矩阵，其中 n 是顶点的数量，或者至少我们需要两个 dist 矩阵。一个将当前的最短路径存储在顶点 k-1 内，另一个存储在顶点 k 内的最短路径，然后第一个存储在 k+1 内的最短路径，.... 我们如何才能将新的最短路径距离存储在顶点内k 在原始矩阵中的顶点 k-1 内的距离？

这张图片显示我们需要 D0, D1, D2....D(n)

我有一个包含数字 0 和 1 的邻接矩阵。如果从一个节点到另一个节点没有边，则该字段将为 0，否则该字段将标记为 1。

那么，如果邻接矩阵中的某个字段为0，则节点之间不存在边，否则存在权重为1的边。

现在，我已经应用 Floyd 算法来找出从任何节点到其他节点的最短路径。但我没有得到正确的解决方案。

这是我的弗洛伊德算法实现。

我已经设置了 0 INT_MAX，以便为算法构建标准矩阵，但我没有得到正确的解决方案。

另外，这是我的矩阵的一个例子：

将矩阵应用于算法后，矩阵中的任何 0 都将转换为INT_MAX. 我希望得到 2 或 1 的权重，但我得到了意想不到的值，例如 -2712323 ...

我有一个这样的图表：

我实现了这样的图形数组：

K只有 4 个单元格，它显示顶点是否连接到它的四个相邻顶点。例如：

它表明 vertex(1, 1) 连接到 2 个顶点。

我知道用于正常类型图形的 Floyd Warshall 算法。但是我怎样才能为这种图实现 Flyod Warshall 算法呢？

谢谢。

给定一个 DAG 的邻接列表Map<Vertex, Set<Vertex>>，我想计算每个顶点的可达性（即是否存在从 u 到 v 的路径）。

static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}

我知道使用 Floyd-Warshall 是可能的O(V^3)

但是我有一个稀疏图（和一个邻接表），那么最快的方法是什么？

我想使用 Floyd-Warshall 算法来找到两个顶点之间的最短路径。该矩阵位于 ArrayList<ArrayList<Integer>> 中。它总是相当小，例如 4x4 或 8x8 矩阵。

在我的课堂上，我已经有一个距离矩阵。我只是想创建“最短路径”矩阵。但它不起作用。它错误地填充了我的矩阵。

我真的希望有人可以看看这个并解释什么是错的。

我的距离矩阵是：

测试输出为：

预期的：

我已经注释掉了我的测试输出。distance是我的矩阵，具有顶点之间距离的整数值。在我的矩阵中，i是 y 并且j是 x。

我读过关于 Floyd 和 Dijkstra 的文章，但他们通过节点之间的最小边长找到最短路径

如何通过遍历最小节点数在有向图中找到最短路径？

这是问题链接：http ://codeforces.com/contest/295/problem/B

Greg 有一个加权有向图，由 n 个顶点组成。在此图中，任何一对不同的顶点在它们之间在两个方向上都有一条边。Greg 喜欢玩图表，现在他发明了一个新游戏：

游戏由 n 个步骤组成。在第 i 步，Greg 从图中删除了顶点号 xi。当 Greg 删除一个顶点时，他也删除了所有进出该顶点的边。在执行每一步之前，Greg 想知道所有剩余顶点对之间最短路径的长度总和。最短路径可以通过任何剩余的顶点。帮助 Greg，在每一步之前打印所需总和的值。

输入：

第一行包含整数 n (1 ≤ n ≤ 500) — 图中的顶点数。

接下来的 n 行每行包含 n 个整数 — 图邻接矩阵：第 i 行中的第 j 个数 aij (1 ≤ aij ≤ 105, aii = 0) 表示从顶点 i 到顶点 j 的边的权重.

下一行包含 n 个不同的整数：x1, x2, ..., xn (1 ≤ xi ≤ n) — Greg 删除的顶点。

输出：

打印 n 个整数——第 i 个数字等于第 i 步之前所需的总和。

因此，基本上我的方法是在删除任何顶点之前运行 Floyd-Warshall 算法，对于删除，我只需将要删除的顶点的值设置为INT_MAX行和列中的邻接矩阵中的值。

基本上，这个循环在main

这是我对 Floyd Warshall 算法的实现：

这里，val是我制作的全局 3-D 矩阵，arr包含要删除的顶点。但是，当我运行此逻辑时，它仅在最初给出正确答案，即没有删除任何顶点。但在那之后，它给出了一个错误的值。我不明白为什么？我的逻辑不正确吗？