问题标签 [floyd-warshall]

我正在寻求一些以视觉方式展示 Floyd-Warshall 有用性的想法。到目前为止，我能想到的只是生成一个随机图，允许用户选择开始/结束并突出显示最短路径。有哪些更有趣但更简单的寻路有用性演示？

如果保证有对称邻接矩阵，是否有降低 Floyd-Warshall 运行时常数因子的优化？

我试图用这个逻辑来理解邻接矩阵发生了什么，但我很困惑它所说的关于 abcd 的间隔......

谁能解释这里发生了什么？

谢谢（标记为 java 作为它向我们展示的语言，所以如果有人发布任何代码示例，他们可以看到它是用该语言编写的）

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

这是代码：

我的大学有一项任务，已经成功实施了 Dijkstra 和 Bellman-Ford，但我在这方面遇到了麻烦。一切看起来都很好，但它并没有给我正确的答案。

这是代码：

我正在使用我制作的这个图表示例：

意味着我们有 6 个顶点（1 到 6）和 7 个边（1,2），权重为 4... 等等。

如果有人需要更多信息，我愿意提供，只是厌倦了查看此代码而没有发现错误。

我正在修改图形实现以使用Floyd 算法计算所有对最短路径矩阵。该图具有邻接链表和矩阵实现。现在我使用邻接矩阵，因为它需要这个算法。

我的问题是如何引用 weight_matrix 元素以便进行比较？这是对象矩阵中的边缘类：

首先，一点背景知识：我正在使用基本图算法（Dijkstra、Floyd-Warshall、Bellman-Ford 等）构建一个简单的图类，以用作即将举行的编程竞赛的参考表。

到目前为止，我有一个 Floyd-Warshall 的功能版本，但缺点是到目前为止它只让我得到两个节点之间的最短距离值，而不是最短路径。最好我希望在算法本身内进行路径构建，而不必调用另一个函数来重建它。

以下是有关我正在使用的数据结构的一些信息：

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

这是我正在使用的示例图形数据：

这是“路径”变量中所需的值（通过从每个节点运行 Dijkstra 获得）：

这是我目前用于算法的代码的链接：（通过 PasteBin）。

任何帮助将不胜感激！

编辑：我尝试了维基百科的代码来生成路径矩阵，结果如下：

它有点工作，但在表示“单个”步骤时存在问题。例如，从节点 0 到节点 1 的路径在任何地方都是未定义的。（不过，感谢 Nali4Freedom 的建议）

我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法。我知道 Dijkstra 找到了从一个节点到所有其他节点的最佳路线，而 Floyd-Warshall 找到了所有节点配对的最佳路线。

我的问题是，如果我在每个节点上运行 Dijkstra 的算法以找到所有配对之间的最佳路线，它会比 Floyd 的算法更有效。

Dijkstra 的运行时间为 O(E + VlogV)，其中 Floyd 的运行时间为 O(V ³ )。如果 Dijkstra 失败，在这种情况下它的运行时间是多少？谢谢！

我正在尝试实现 Floyd-Warshall 算法（所有对最短路径）。在下面的代码中，当我输入一些数字时，它会给出最后一个数字作为输入。我知道代码不完整。

现在我应该怎么做才能打印每个 i 和 j 的最短路径？或者你建议我做什么来完成这段代码。谢谢。

我想在 Prolog 中编写这个算法，首先我需要从图表列表中创建一个矩阵。我以前做过（也在你们中的一些人的帮助下，伙计们），但现在我不知道如何将它存储在列表列表中（我认为这是 prolog 情况下的最佳方法）。我想我可以从那里继续（在每个算法中都有三重 for 循环）。程序的逻辑对我来说并不难，而是如何处理数据。很抱歉打扰并提前致谢！

我的矩阵生成器：

显然我的老师认为，即使我们没有时间学习东西（也没有足够的例子），我们也应该继续前进，所以我现在需要知道如何在 clisp 中制作 Floyd-Warshall 和 Warshall 的算法。

正如我对 prolog 所做的那样，我的问题是从图中生成邻接矩阵，在这种情况下，它将是一个列表列表，例如：

那应该产生：

我有这个：

任何帮助是极大的赞赏。

另外，还有点题外话：如果我能解决我自己的问题，我是否应该回答自己以便得到答案？