c++ - Floyd 的最短路径算法 C++

Question

我已经在 C++ 中为加权有向图实现了一个 Floyd 算法的函数，该函数可以正常工作，除了当我生成一个路径矩阵，该矩阵在尝试到达目的地时给出下一个节点时，它将顶点放在目的地之前，而不是矩阵中源的下一个节点。距离矩阵 (dist) 是正确的，如果源和目的地之间最多只有一个节点，则整个路径矩阵是正确的。因此，如果从顶点 i 到 j 有很长的最短路径，那么 path[i][j] 应该等于连接到 i 的 k 值，而不是连接到 j 的 k 值，我不知道为什么。该功能如下所示。

void floyd(const Graph<City>& g, double**& dist, int**& path)
{
    int n = g.size();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            path[i][j]=0;
            if (i==j)
                dist[i][j]=0;
            else if (!g.isEdge(i, j))
                dist[i][j]=INFINITY;
            else
                dist[i][j]=g.retrieveEdge(i, j);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if ((dist[i][k]!=INFINITY) && (dist[k][j]!=INFINITY) && k!=i && k!=j && i!=j)
                {
                    if ((dist[i][j]) > (dist[i][k]+dist[k][j]))
                    {
                        path[i][j]=k;
                        dist[i][j]=dist[i][k]+dist[k][j];
                    }
                }
            }
        }
    }
}

Answer 1

So if there are long shortest paths from vertex i to j, then path[i][j] should equal a k value connected to i but instead its a k value connected to j and I cannot figure out why.

不幸的是，两者都不是。在您的实现中没有任何东西可以保证 path[i][j] 应该等于紧跟在 i 之后的 k 值，并且您的观察到 path[i][j] 当前是紧接在 j 之前的 k 值也是不正确的。 (请多试几个 sample 来验证第二点。)

你的实现唯一能保证的是顶点 path[i][j] == k 位于 某处 到顶点 的最短路径中>i 到顶点 j。

因此您可以通过以下方式递归检索路径:

get_path(i, j):
    k = path[i][j]
    get_path(i, k) + k + get_path(k, j)

澄清后，there does exist a method您可以在哪里存储 path[i][j]，这样它就是紧跟在 i 之后的顶点。