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