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

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

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

我假设有只在代码中一个愚蠢的错误，但我不能找到它，所以我很感激任何帮助。

来源

2017-07-05 Vajk

为了帮助别人帮助您，我的建议是链接到您正在尝试实现的算法的声明（最好是伪代码，而不仅仅是文本描述），并给出非常小的（3个节点是OK，2节点显示问题？可以1？），完整的例子（即把你的代码放在一个带有主程序的类中，告诉人们如何运行它）。 –

[此链接]（http://www.sanfoundry.com/java-program-implement-floyd-warshall-algorithm/）可能会有所帮助。 – Manindar

的问题是：您正在使用在您的实现两个相反的方式值为0：

要发出信号存在x和y之间没有边，设置graph[x][y]为0，因为由支票目击if (graph[x][y] > 0),if (graph[y][j] > 0)
为了信号在两个节点之间的距离0。

所以你的对角线条目实际上告诉你：什么是最小的非平凡的周期涉及我的顶点？

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

来源

2017-07-05 17:55:17

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

回答

相关问题