c++ - 使用修改后的弗洛伊德 Warshall 打印给定节点的黑白最短路径

Question

我阅读了Wikipedia给出的方法，通过修改 Floyd Warshall 算法在图中以两个给定点打印短路径。我对此进行了编码，但它并没有真正给出预期的输出：

1. 将图中的所有元素初始化minimumDistanceMatrix[i][j]为各自的权重，将矩阵中的所有元素初始化shortestPathCalculatorMatrix [i][j]为-1。

2. 然后 ：

   // Find shortest path using Floyd–Warshall algorithm
   
   for ( unsigned int k = 0 ; k < getTotalNumberOfCities() ; ++ k)
      for ( unsigned int i = 0 ; i < getTotalNumberOfCities() ; ++ i)
         for ( unsigned int j = 0 ; j < getTotalNumberOfCities() ; ++ j)
             if ( minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j] < minimumDistanceMatrix[i][j] )
             {
                   minimumDistanceMatrix[i][j] = minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j];
                   shortestPathCalculatorMatrix [i][j] =  k;
             }
   

3. 然后 ：

   void CitiesMap::findShortestPathListBetween(int source , int destination) 
   {
        if( source == destination || source < 0 || destination < 0)
           return;
   
        if( INFINITY == getShortestPathBetween(source,destination) )
           return ;
   
        int intermediate = shortestPathCalculatorMatrix[source][destination];
   
        if( -1 == intermediate )
        {
           pathCityList.push_back( destination );
           return ;
        }
   
        else
        {
           findShortestPathListBetween( source, intermediate ) ;
           pathCityList.push_back(intermediate);
           findShortestPathListBetween( intermediate, destination ) ;
   
           return ;
        }
   }
   

PS：pathCityList是一个向量，在调用之前假定为空findShortestPathListBetween。在此调用结束时，此向量中包含所有中间节点。

有人可以指出我可能会出错的地方吗？

Answer 1

不迭代索引而是迭代顶点要容易得多（也更直接）。此外，每个前驱（通常表示为π，not next）需要指向它的前驱，而不是当前的临时顶点。

给定一个 | 五|×| 五| 距离的邻接矩阵dist，初始化为无穷大，a | 五|×| 五| next带有指向顶点的指针的邻接矩阵，

for each vertex v
    dist[v, v] ← 0
for each edge (u,v)
    dist[u, v] ← w(u,v)  // the weight of the edge (u,v)
    next[u, v] ← u

for each vertex k
    for each vertex i
        for each vertex j
            if dist[i, k] + dist[k, j] < dist[i, j] then
                dist[i, j] ← dist[i, k] + dist[k, j]
                next[i, j] ← next[k, j]

请注意，我已更改三个嵌套循环以迭代顶点而不是索引，并且我已修复最后一行以引用前一个节点而不是任何中间节点。

例如，可以在scipy.sparse.csgraph.

路径重建从末尾开始（j在下面的代码中）并跳转到j(at next[i, j]) 的前身，直到到达i.

function path(i, j)
    if i = j then
        write(i)
    else if next[i, j] = NIL then
        write("no path exists")
    else
        path(i, next[i, j])
        write(j)

Answer 2

有点晚了，但上面的代码有缺陷....它不应该next[i][j]=next[k][j]，但找到这个的正确代码是next[i][j]=next[i][k]

在示例输入上自己尝试一下，您将了解为什么这样有效以及为什么前一个错误

Answer 3

这是下面的实现。为什么不尝试它的问题！ 享受CP！！

   // g[][] is the graph
   // next[i][j] stores vertex next to i in the shortest path between (i,j)
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          if(g[i][j]==0)g[i][j]=inf;  // there is no edge b/w (i,j)
          else next[i][j]=j;    // if there is an edge b/w i and j then j should be next to i
        }
      }

      for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            if(g[i][j]>g[i][k]+g[k][j]){
              g[i][j]=g[i][k]+g[k][j];
              next[i][j]=next[i][k];  // we found a vertx k next to i which further decrease the shortest path b/w (i,j) so updated it
            }
          }
        }
      }
      // for printing path
      for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
          int u=i,v=j;
          print(u+" ");
          while(u!=v){
            u=next[u][v];
            print(u+" ");
          }
          print("\n");
        }
      }