用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去。