我已经尝试了一个星期,让路径查找适用于我正在开发的游戏。我正在使用this implementation Floyd Warshall 的算法。我相信我已经成功地将问题范围缩小到这个循环内:
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
我不知道到底是什么导致了循环中的问题,或者我是否误解了算法的某些内容。
最佳答案
从结果来看:
[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 实现看起来完全没问题。也许您应该在其他地方检查您的错误,例如最短路径路由的恢复,该错误更容易出现错误。
关于Floyd Warshall 算法的 Java 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12574847/