用Floyd-Warshall算法寻找迷宫路径

Question

我正在尝试使用Floyd算法来生成一个通过迷宫的最快路径矩阵，该迷宫有98个路点(位于每个迷宫顶点)。当算法运行时，它填充两个矩阵-距离矩阵(具有两个节点之间的最优距离)和路径矩阵(具有要转到的下一个节点，以获得任意两个节点之间的最佳路径)。

距离矩阵是用我在前面代码中生成的邻接矩阵初始化的。我还生成了一个数据结构，其中包含指向每个路点的四个可能的邻居路点的指针，但我在生成路径矩阵时没有使用此数据结构。

下面是我的c#代码：

        // Initialize distance path matrix
        distanceMatrix = adjacencyMatrix;

        // Initialize path matrix
        int N = (WaypointList.Count);
        pathMatrix = new int[N, N];

        for (int i = 0; i < N; i++)
            for (int t = 0; t < N; t++)
                pathMatrix[i,t] = t;

        // Floyd-Warshall algorithm            
        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j <= i; ++j)
                {
                    int currentCombo = distanceMatrix[i, k] + distanceMatrix[k, j];
                    if (currentCombo < distanceMatrix[i, j])
                    {                            
                        distanceMatrix[j, i] = distanceMatrix[i, j] = currentCombo;
                        pathMatrix[j, i] = pathMatrix[i, j] = k;
                    }
                }

我认为我错误地计算了路径矩阵，因为使用此代码生成的路径矩阵的机器人在大多数情况下都会失败(因为路径矩阵被告知要穿墙，等等)。

我已经盯着这个代码看了几个小时了，我被自己做错了什么弄糊涂了。如何生成在迷宫导航代码中使用的正确路径矩阵？

Answer 1

在设置pathMatrix[i, j] = k时，假设这意味着从节点i到j的路径将从节点k开始。但实际上，这意味着从i到j的路径将在某个时候通过k，而不一定是第一步。

假设有一条从i到j的路径，您需要做的如下所示

target = j
while there is no edge from i to target:
    target = pathMatrix[i, target]

这会将target设置为从i转到的下一个节点。