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

首先，有一点背景：我正在构建一个带有基本图算法（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

和这里的期望的值在“路径”变量中（通过从每个节点运行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的建议）

来源

2010-10-25 Mr. Llama

如果我正在阅读这个权利，根据'graph'的第一行，只有一个来自节点＃0的边，并且它导致节点＃1。所以'path'的第一行（或者第一列）应该是'Inf 1 1 1 1 1'。我错过了什么？ – Beta 2010-10-25 23:15:26

啊，我看你怎么会觉得困惑。 'graph'中的每一行列出了从该节点离开的边，而'path'中的每一行都包含了到达'node＃[row_num]'的路径。例如，正确的“路径”图的第一行意味着要从节点5（col = 5）到达节点0（行= 0），返回路上的下一个节点是节点2.要到达节点0从节点2我们使用节点4，然后节点3，然后节点1，然后最终在我们的目的地与节点0. – 2010-10-26 05:07:40

Huzzah！

我在结果好辛苦盯从添加维基百科的代码片段，我想出了一个适配器，它的成果转化为我的结果，而无需调用单独的函数：

// 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)的垫脚石，那么它会挖掘直到找到它所通向的地方。

感谢您的帮助，猜猜我只是需要有人大声思考！

来源

2010-10-25 22:39:06

维基百科有一些很好的信息和pseudocode。基本上你只需填写| V | x | V | 'next'矩阵，其中元素i，j包含您需要从节点i到节点j获取的顶点的索引。从i到j的最短路径可以作为从i到下一个[i] [j]和从下一个[i] [j]到j的路径。你继续像这样递归地分解路径，直到你有完整的路径。

来源

2010-10-25 21:26:14

相信我，我给了它一个去，但我的设置的工作方式（默认值设置为INF）它doesn工作不正常。：\ – 2010-10-25 21:40:00

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

回答

相关问题