Java Floyd 算法的实现不适用于无向图

Question

我得到了以下 Floyd 算法的实现，该算法用于在加权图中查找最短路径。结果是所有顶点之间的最短路径矩阵：

class FloydWarshall {

static int graph [][] = {   {0, 5, 3},
                            {5, 0, 0},
                            {3, 0, 0}
                        };

public static void main(String args[]) {

    int N=graph.length;
    int y, x, j;

    for (y = 0; y < N; y++)
        for (x = 0; x < N; x++)
            if (graph[x][y] > 0) 
                for (j = 0; j < N; j++)
                    if (graph[y][j] > 0)
                        if ((graph[x][j] == 0) || (graph[x][y] + graph[y][j] < graph[x][j]))
                            graph[x][j] = graph[x][y]+graph[y][j];
    for (y = 0; y < N; y++) {
        for (x = 0; x < N; x++)
            System.out.print(graph[y][x] < 0 ? "  "+graph[y][x] : " "+graph[y][x]);
        System.out.println();
    }
}

}

奇怪的是，即使它在工作，它也不会为无向图计算从顶点到自身（应该为 0）的正确距离。例如下图：

{0, 5, 3}
{5, 0, 0}
{3, 0, 0}

得到输出：

6 5 3
5 10 8
3 8 6

而不是：

0 5 3
5 0 8
3 8 0

我假设代码中存在一个愚蠢的错误，但我无法找到它，所以非常感谢您的帮助。

Answer 1

问题如下：您在实现中以两种相反的方式使用值 0：

为了表示 x 和 y 之间不存在边缘，您将 graph[x][y] 设置为 0，如检查 if (graph[x][y] > 0) 所示, if (graph[y][j] > 0)
表示两个节点之间的距离为 0。

所以你得到的对角线条目实际上告诉你：涉及我的顶点的最短非平凡循环是什么？

我建议您要么使用非常大的数字（Integer.MAX_VALUE，注意溢出！）来表示非边，要么更好：将邻接信息存储在一个完全独立的矩阵中。

Java Floyd 算法的实现不适用于无向图

Java implementation of Floyd's algorithm doesn't work for undirected graphs

java

algorithm

shortest-path

floyd-warshall