0

我已经尝试了一周来为我正在开发的游戏寻找路径。我正在使用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

我不知道究竟是什么导致了循环中的问题，或者我是否对算法有误解。

4

1 回答 1

1

从结果来看：

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

我几乎可以猜到发生了什么。您可能已将所有内容初始化D[i][j]为. 所以前 3 个更新是, 。但只能更新。1D[i][i]Integer.MAX_VALUED[i][i] = D[i][0] + D[i][0]k = 0i = 1..3D[0][0]d[0][1] + d[1][0]

您对 floyd-warshall 的实现看起来完全没问题。也许您应该在其他地方检查您的错误，例如恢复最短路径路径，这更容易出错。

于 2012-09-25T03:15:54.907 回答