Floyd Warshall算法的Java實現

我一直在嘗試一個星期才能找到適合我正在開發的遊戲的路徑。我使用Floyd Warshall算法的this implementation。我相信我已經成功地縮小問題是在這個循環中：Floyd Warshall算法的Java實現

for(int k = 0; k < nodes.length; k++) 
    for(int i = 0; i < nodes.length; i++) 
     for(int j = 0; j < nodes.length; j++) 
      if(D[i][k] != Integer.MAX_VALUE 
      && D[k][j] != Integer.MAX_VALUE 
      && D[i][k] + D[k][j] < D[i][j]){ 
       D[i][j] = D[i][k]+D[k][j]; 
       P[i][j] = nodes[k]; 
      }

我已經有4個節點的測試是每一個節點連接到所有其他節點和所有連接都爲1的重量這裏的循環前所有相關變量的值。

for(Node n:nodes)System.out.println(n.pos.toString() + " " + n.index);

輸出：

[x: 4, y: 4] 0 
[x: 4, y: 5] 1 
[x: 5, y: 4] 2 
[x: 5, y: 5] 3

這是作爲預期

for(Edge e:edgeList) 
    System.out.println(e.from.pos.toString() + " " + e.to.pos.toString());

輸出：

[x: 4, y: 4] [x: 5, y: 4] 
[x: 4, y: 4] [x: 4, y: 5] 
[x: 4, y: 4] [x: 5, y: 5] 
[x: 4, y: 5] [x: 4, y: 4] 
[x: 4, y: 5] [x: 5, y: 4] 
[x: 4, y: 5] [x: 5, y: 5] 
[x: 5, y: 4] [x: 4, y: 4] 
[x: 5, y: 4] [x: 4, y: 5] 
[x: 5, y: 4] [x: 5, y: 5] 
[x: 5, y: 5] [x: 4, y: 4] 
[x: 5, y: 5] [x: 5, y: 4] 
[x: 5, y: 5] [x: 4, y: 5]

這也是預期。

for(int[] ia:D){ 
    for(int a:ia)System.out.print(a + " "); 
    System.out.print("\n"); 
}

輸出：

2147483647 1 1 1 
1 2147483647 1 1 
1 1 2147483647 1 
1 1 1 2147483647

這也符合市場預期。

P = new Node[nodes.length][nodes.length]; 
for(int k = 0; k < nodes.length; k++) 
    for(i = 0; i < nodes.length; i++) 
     for(int j = 0; j < nodes.length; j++) 
      if(D[i][k] != Integer.MAX_VALUE 
      && D[k][j] != Integer.MAX_VALUE 
      && D[i][k]+D[k][j] < D[i][j]){ 
       D[i][j] = D[i][k]+D[k][j]; 
       P[i][j] = nodes[k]; 
       System.out.println(nodes[k].pos.toString() + " " + k); 
      }

輸出：

[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 5] 1

這是我認爲這個問題是，我所期望的輸出包含所有不同的節點，這裏只發現了兩個節點在getShortestPath功能工作。我相信這將是循環的正確輸出，順序應該是無關緊要的，據我瞭解。

[x: 4, y: 4] 0 
[x: 4, y: 5] 1 
[x: 5, y: 4] 2 
[x: 5, y: 5] 3

我不知道究竟是什麼導致循環，或者如果我誤解了一些關於算法的問題。

來源

2012-09-25 Luka

如果您向我們展示您期望的輸出，那將會有很大幫助。說「這不是預期的」並沒有多大幫助，因爲有很多可能的「其他」結果。 – Bohemian

從結果：

[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 5] 1

我幾乎可以猜到發生了什麼事。您可能已初始化所有D[i][j]至1，但是D[i][i]至Integer.MAX_VALUE。因此前3次更新爲D[i][i] = D[i][0] + D[i][0]，其中k = 0,i = 1..3。但是D[0][0]只能更新爲d[0][1] + d[1][0]。

你的floyd-warshall實現看起來完全沒問題。也許你應該在其他一些地方檢查你的bug，比如恢復最短路徑的路由，這個路由更容易出錯。

來源

2012-09-25 03:15:54 chyx

不幸的是，來自實現的initializeWeight函數與我得到的完全一樣，所以這不是什麼錯誤，我已經將D變量的值添加到我的問題中了。謝謝你的嘗試。 – Luka

Floyd Warshall算法的Java實現

回答

相關問題