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

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)

  /li>

• 表示两个节点之间的距离为 0。

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

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