c++ - 使用修改后的 floyd 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 ;
        }
   }
   

P.S:pathCityList 是一个 vector ，在调用 findShortestPathListBetween 之前假定它为空。在此调用结束时，此 vector 中包含所有中间节点。

有人可以指出我可能哪里出错了吗？

Answer 1

不遍历索引而是遍历顶点更容易(也更直接)。此外，每个前驱(通常表示为 π，而不是 next)需要指向它的predecessor，而不是当前的临时顶点。

给定一个|V|×|V|距离的邻接矩阵 dist，初始化为无穷大，|V|×|V|邻接矩阵 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的前导(在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)