代码之家  ›  专栏  ›  技术社区  ›  Mr. Llama

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

  •  5
  • Mr. Llama  · 技术社区  · 16 年前

    首先,一点背景知识:我正在用基本的图形算法(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

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

    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
    

    以下是我当前用于算法的代码的链接: (via PasteBin) .

    编辑: 我试过了 Wikipedia's code 生成路径矩阵,结果如下:

    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的建议)

    2 回复  |  直到 13 年前
        1
  •  2
  •   Mr. Llama    16 年前

    胡扎!

    我仔细研究了一下添加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
    

    (mid_node == INF) 通过添加边(如果它存在于原始图中)。或者,如果它指向的节点只是指向目标节点的垫脚石 (this->path[mid_node][end_node] != INF) 然后它挖掘,直到找到它通向的地方。

        2
  •  1
  •   David Brown    16 年前

    维基百科有一些很好的信息 pseudocode