使用修改的floyd warshall打印给定节点的最短路径b/w

Question

我阅读了维基百科给出的方法,通过修改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

维基百科的文章太可怕了.除了错误表示(在我看来)Floyd-Warshall算法的规范形式,它还提出了一个错误的伪代码.

更容易(也更直接)不迭代索引而是迭代顶点.此外,每个前任(通常表示?为非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]

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

可以在Algoritmy.net找到解释为什么这是正确的,以及前任矩阵是如何工作的.

以上需要一些初始化.幸运的是这很简单,因为我们已经知道每个节点的第一前身:如果有一个直接的路径dist来next,那么scipy.sparse.csgraph是j的前身.如果没有直接路径,那么就没有前任.

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)

j只是任何非顶点值的占位符.在面向对象的代码中,这通常是next[i, j]引用/指针.当将图形实现为邻接矩阵时,它可以是不对应于顶点的任何索引,例如-1或| V | +1.

他们还提供纠正的路径重建:

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]