使用Floyd- and找到所有最短的路径和距离

Question

首先，一个小小的背景:我正在构建一个简单的图形类，使用基本的图形算法(Dijkstra、Floyd、Bellman等)作为即将到来的编程竞赛的参考书。

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

下面是关于我使用的数据结构的一些信息：

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

下面是我使用的示例图形数据：

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

下面是"path“变量中所需的值(通过从每个节点运行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的建议)

Answer 1

哇哈！

我很难看到添加Wikipedia代码片段的结果，我想出了一个适配器将它的结果转换成我的结果，而不需要调用单独的函数：

// 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)的垫脚石，那么它就会挖掘，直到找到它指向的位置。

谢谢你们的帮助，我想我只是需要有人大声地想一想！

Answer 2

维基百科有一些好的信息和伪码。基本上，您只需填写一个从节点i到节点j的顶点索引，其中元素i，j包含从i到j的最短路径，从i到j的最短路径可以作为从I到nexti和从nexti到j的路径。您继续像这样递归地分解路径，直到得到完整的路径为止。