使用 Floyd-Warshall 算法查找所有最短路径和距离

Question

首先，一些背景信息：我正在构建一个简单的图形类和基本的图形算法（Dijkstra、Floyd-Warshall、Bellman-Ford等），以便在即将到来的编程竞赛中作为参考资料使用。

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

这里有一些关于我使用的数据结构的信息： vector< vector<int> > graph //包含从每个节点到其他每个节点的距离值（如果没有边，则graph [1] [3]包含从节点＃1到节点＃3的边长，值为INF vector< vector<int> > path //包含到达给定节点的“跳板”。path [st_node] [end_node]包含从end_node -> st_node的下一个节点的值 这是我使用的示例图形数据：

INF 10  INF INF INF INF
INF INF 90  15  INF INF
INF INF INF INF INF 20
INF INF INF INF 20  INF
INF INF  5  INF INF INF
INF INF INF INF INF INF

这里是期望的数值，应该在“路径”变量中（通过从每个节点运行Dijkstra获得）：

INF  0   4   1   3   2
INF INF  4   1   3   2
INF INF INF INF INF  2
INF INF  4  INF  3   2
INF INF  4  INF INF  2
INF INF INF INF INF INF

这是我目前正在使用的算法代码链接: (通过PasteBin)。

非常感谢您的任何帮助！

编辑: 我尝试使用维基百科的代码来生成路径矩阵，以下是结果:

INF INF  4   1   3   4
INF INF  4  INF  3   4
INF INF INF INF INF INF
INF INF  4  INF INF  4
INF INF INF INF INF  2
INF INF INF INF INF INF

它有点能用，但在表示“单个”步骤时存在问题。例如，从节点0到节点1的路径在任何地方都是未定义的。(但仍然感谢Nali4Freedom的建议)

- Mr. Llama

---

如果我理解正确的话，根据graph的第一行，只有一个从节点#0出发的边，它通向节点#1。因此，path的第一行（或者可能是第一列）应该是Inf 1 1 1 1 1。我错过了什么吗？ - Beta

啊，我明白你为什么会感到困惑了。在graph中，每一行列出了从该节点离开的边，而在path中，每一行包含到达node #[row_num]的路径。例如，正确的path图表的第一行表示从节点5（列=5）到达节点0（行=0）时，下一个回程的节点是节点2。要从节点2到达节点0，我们使用节点4，然后是节点3、节点1，最后到达目的地节点0。 - Mr. Llama

Answer 1

太好了！

我仔细观察了添加维基百科代码片段的结果，并设计了一个适配器，可以将其结果转换为我的结果，无需调用单独的函数：

// Time to clean up the path graph...
for (int st_node = 0; st_node < this->size; st_node++)
{
    for (int end_node = 0; end_node < this->size; end_node++)
    {
        int mid_node = this->path[st_node][end_node];

        if (mid_node == INF)
        {
            // There is no mid_node, it's probably just a single step.
            if (this->graph[st_node][end_node] != INF)
            {
                this->path[st_node][end_node] = st_node;
            }

        } else {
            // The mid_node may be part of a multi-step, find where it leads.
            while (this->path[mid_node][end_node] != INF)
            {
                if (this->path[mid_node][end_node] == mid_node) { break; }  // Infinite loop
                if (this->path[mid_node][end_node] == INF) { break; }   // Dead end

                mid_node = this->path[mid_node][end_node];
            }

            this->path[st_node][end_node] = mid_node;

        }   // IF mid_node
    }   // FOR end_node
}   // FOR st_node

本质上，这是为了弥补从节点A到节点B只有一步 (mid_node == INF) 的情况，通过添加原始图中存在的边来实现。或者，如果它指向的节点只是通往目标节点的一个垫脚石 (this->path[mid_node][end_node] != INF)，那么它会一直挖掘直到找到其指向的位置。

感谢大家的帮助，我想我只是需要有人公开表达自己的想法！

- Mr. Llama

Answer 2

维基百科有一些关于pseudocode的好信息。基本上，您只需填充一个|V|x|V|的“next”矩阵，其中元素i，j包含了从节点i到节点j所需前往的顶点的索引。然后，从i到j的最短路径可以作为从i到next[i][j]的路径以及从next[i][j]到j的路径给出。您可以像这样递归地分解路径，直到获得完整路径。

- David Brown

---

相信我，我已经尝试过了，但是由于我的设置方式（默认值设置为INF），它无法正常工作。：\ - Mr. Llama