问题标签 [floyd-warshall]

我们正在开展一个小型学校项目，用 Floyd-Warshall 用 java 实现一个算法（我们不能使用另一个）。

该算法运行良好，我们使用成本数组作为 Floyd-Warshall 算法的输入。

老师有 5 个文件要检查，我们传递了 4 个，但第 5 个是一个包含 15 000 个顶点的数组，这意味着一个包含 15 000 * 15 000 个整数的数组。

Java因为内存而拒绝使用它。你知道如何通过这个吗？

谢谢

我需要一双新的眼睛，由于某种原因，它没有生成正确的序列和距离矩阵，以下是我的实现。

这是在 C# 中，DistanceMatrix 是一个双 [,] 而 SequenceMatrix 是一个字符串 [,]

这些启动如下： http: //puu.sh/951Tz/5ef27e3996.png

出于某种原因，我得到以下输出：

任何指针将不胜感激，如果您需要更多信息，我将在此页面上 F5 :)

初始化后的距离矩阵

我正在尝试使用 Floyd-Warshall 算法创建一个简单的程序来计算两对或多对节点之间的最短路径。

我正在使用一个类Village来表示节点，并使用一个类来表示Road所述节点之间的道路。通过代码，我还调用了一个类TransportRequest，该类代表我需要从中生成最短路径的两个节点。

上面的代码似乎在大多数随机生成的节点和距离上都可以正常工作，但是在少数情况下会失败，例如下面的代码；

如果我尝试计算从节点 A 到节点 E 的最短路径，答案总是 A > E（总共 100）而不是 A > B > C > D > E（总共 37）。

每个节点之间的道路是双向的，这意味着从 A 到 B 和 B 到 A 都是 10，在这种情况下。

使用每个节点对之间的正确距离正确填充了矩阵 dist[]。如果没有连接这对节点的道路，我将默认距离设置为 1000000 个单位。

我在不同的论坛（包括这个）上搜索了多个问题，但似乎没有一个可以解决这个问题。我相信该算法已正确实施，但我看不出在某些情况下它在哪里以及为什么不能正常工作。

我非常感谢在这个问题上的帮助，因为我已经努力解决这个问题一个多星期了。

提前谢谢了。

这可能是一个不好的问题，因为我的代表很低，但我已经研究了几个小时的其他解决方案，我的代码似乎与我遇到的工作解决方案几乎相同。请不要忽略基于低代表的问题。

输出矩阵 d[][] 包含给定顶点对之间最短路径的（不正确）长度。已经使用了networkx库中为Python提供的解决方案。

作为摘录，已经提供了n=20的结果。我没有打印出大于无穷大（即 99999）的路径，因为存在溢出。

这是图表的样子：

我的 Floyd-Warshall 算法实现（C）

Floyd-Warshall 算法的 Networkx 解决方案（Python）

执行：

测试客户端（Python）

想象一下，给定一个加权无向完全图，其中 n 个节点具有非负权重 Cij，其中 i = j Cii = 0，并且 i != j Cij > 0。假设你必须找到任意两个节点之间的最大最短路径节点 i 和 j。在这里，您可以轻松地使用 Floyd-Warshall，或使用 Dijkstra n 次，或其他任何方法，然后在所有 n^2 最短路径中找到最大值。

现在假设 Cij 不是常数，而是可以取两个值，Aij 和 Bij，其中 0 <= Aij <= Bij。我们也有 Aii = Bii = 0。假设您还需要找到最大最短路径，但约束条件是 m 边必须取值 Bij 和其他 Aij。并且，如果 m > n^2，则所有边都等于 Bij。但是，当找到最短路径 i -> p1 -> ... -> pk -> j 时，您对最坏的情况感兴趣，因为在该路径上您需要选择那些边来获取 Bij 的值，例如如果您在其方向上有固定节点，则该路径值最大。

例如，如果您有长度为 4 iklj 的路径，并且在该路径上的最优解中，只有一个权重更改为 Bij，而其他取 Aij 的值。并设 m1 = Bik + Akl + Alj，m2 = Aik + Bkl + Alj，m3 = Aik + Akl + Blj，该路径的值为 max{m1, m2, m3}。因此，在 i 和 j 之间的所有路径中，您必须选择一个使得最大值（如本例中所述）最小的（这是最短路径定义的一种变体）。你必须对所有对 i 和 j 都这样做。

您没有得到约束，您需要在每条路径上改变多少，而是给出 m 的值，即在完整图中应该变化的权重的数量。问题是找到最短路径的最大值，如前所述。

另外，我的问题是：这是 NP 难题，还是存在一些多项式解决方案？

有人可以在 for 迭代中给我这个过程的时间复杂度吗？这段代码就是 FloydWarshall 算法的“重构路径”部分。prev[n][n] 是最短路径中源节点和目标节点之间的节点矩阵。printAllSP 在迭代中运行 n^2 次，我无法真正弄清楚它每次执行的递归调用次数，只知道取决于 i 值（max n）、j 值（max n）和插入 i 和 j 之间最短路径的 k (???) 节点数，根据我的评估，包括这部分在 On^4 中运行的 for 循环，但总算法复杂度为 On^3。请启发我！

我很困惑，并试图弄清楚如何将此图形数据放入邻接矩阵中。

这是来自文本文件的一些示例输入：

这就是矩阵的外观

这将是某种多维数组，但我不知道如何将输入转换为一个。任何帮助，将不胜感激。

我在 python 中工作。

谢谢！

在 Floyd-Warshall 算法中，计算任意一对顶点的最短路径成本。额外的簿记使我们能够将实际路径（顶点列表）保持在最短路径上。

如何扩展 Floyd-Warshall 以便为任何一对顶点找到前 K 个最短路径？例如，对于 K=3，结果会是计算和维护 3 条最短路径吗？

我一直在使用 Sedgewick 的Java 实现。

我知道这个问题之前已经回答过好几次了，但我检查了所有以前的答案来纠正我的情况，但它没有帮助。

我需要做的是并行化我的循环，以便并行处理每个城市（或内部循环）。但是在使用 parfor 时出现错误“无法对 parfor 中的变量 A 进行分类”。二维矩阵的大小固定为 n X n。我不知道看到问题。请帮帮我...

我提供的 c 实现是使用 mpi.h 完成的。使用 mpicc。我需要实现的是应该有 n 个进程，每个进程负责找到从本地城市到所有其他城市的最短路径。

每个案例都不同。就我而言：

这是我计算最短路径的函数：

就我被告知我需要的方法而言，我已经有了该程序所需的框架。但是，除此之外，我在弄清楚如何开始编写这个程序时遇到了麻烦。详细情况如下。 我不是要求为我完成我的程序，实际上我只是对如何开始感到困惑。我知道我需要读取用户输入来获取文本文件，我们在我的大学使用扫描仪，但我不知道这是否需要在构造函数中、main 中或其他方法中。

1. 接受单个命令行参数 - 即包含行分隔的字符串对列表的文本文件。这些字符串对将表示依赖图中的边。例如，读取为：A.java B.java 的行表示从 A.java 到 B.java 的依赖边。表示上图的文件可能如下所示： Main.java A.java A.java B.java

2. 将从文件中读取的每个字符串映射到唯一的整数标识符。这种映射将使将文件名转换为数组索引变得容易。

3. 将每个唯一整数标识符（从上面）映射回原始字符串。

4. 计算表示字符串之间依赖关系的邻接矩阵。

5. 对邻接矩阵执行传递闭包操作以生成表示字符串之间传递依赖关系的新闭包矩阵。执行此操作的一种简单方法是 Floyd-Warshall 算法 - 您可能想对这个主题进行一些研究。

6. 您的输出必须遵循课程网站上示例输出文件所示的格式。课程网站上有一个示例输入文件和相应的输出文件。在此示例中，您的输出必须具有相同的格式。目标是使输出信息具有有吸引力、可读的格式，清楚地表明下面列出的每个方法都可以正常工作。

7. 具有私有字段返回类型的方法，例如 getNameIdMap、getIdNameMap、getRoots 等，而不是返回我们类的内部状态的可变部分，即应该返回该映射的副本（克隆）列表。这样，调用者就可以得到一个完全可用的对象（例如，列表或地图），而不会影响类的内部状态。

您的程序还应提供以下方法：

1. public Map getNameIdMap() - 返回从字符串到唯一整数标识符的映射。整数标识符表示给定字符串的邻接矩阵和闭包矩阵的索引。注意：在 Python 中，返回值必须是一个字典，其中键是字符串，值是整数。

2. public Map getIdNameMap() - 返回从唯一整数标识符到原始字符串的映射。注意：在 Python 中，返回值必须是一个字典，其中键是整数，值是字符串。

3. public int[][] getDependenceGraph() - 返回表示文件之间依赖关系的邻接矩阵。

4. public int[][] getTransitiveDependenceGraph() - 在应用传递闭包操作后返回依赖图。

5. public List getRoots() - 返回一个字符串列表，这些字符串对应于没有其他文件依赖的文件（例如，上面示例中的 Main）。注意：在 Python 中，返回值也是一个字符串列表。

6. public List getLeaves() - 返回一个字符串列表，这些字符串对应于不依赖其他文件的文件（例如，上例中的 B）。注意：在 Python 中，返回值也是一个字符串列表。

7. public void removeLeaf(String leaf) - 从邻接和传递闭包矩阵中删除一个叶子。这意味着如果 X 依赖于 Y 并且 Y 是被移除的叶子，那么 X 对 Y 的依赖也会被消除。这可能会或可能不会使 X 成为新的叶子。考虑在矩阵中使用一个特殊的数字（即，除了 0 和 1）来表示该文件已被逻辑删除。

8. public List firewall(String node) - 计算指定文件的“类防火墙”。在软件工程中，类防火墙概念指出，当对系统进行维护时，只有更改的类和受更改影响的类需要重新测试。注意：在 Python 中，返回值也是一个字符串列表。对于此方法，您应该重新测试间接和直接受影响的类。例如，如果 A 类依赖于 B 类，B 类依赖于 C 类，而你更改了 C 类，那么你应该重新测试 A 类和 B 类。

9. public void printParallelGroups() - 假设我们想要并行编译文件，我们需要识别不会触发其他文件编译的文件；这些是依赖图中的叶子。此方法识别可以并行编译的文件，打印该文件列表，并将它们从图中删除。该方法应重复此过程，直到所有文件都已“编译”。