Floyd warshall实施似乎缺少最短的路径

Question

我正在收集弗洛伊德沃尔斯发现的最短路径.对于此特定图表,1 - > 3的最短路径为5,并且有两个具有此权重的路径:1-> 4-> 2-> 3,1-> 4-> 3.

我不确定显示图表的最佳方式,因此我将使用矩阵,如果您知道更好的替代方案,请随意提出另一种方法.

 //i = infinity, no path exists initially
 //for u==v, 0
    1   2   3   4
1|  0   i   8   2
2|  i   0   2   i
3|  i   7   0   6
4|  i   1   3   0

因此,当我运行我的代码时,我得到的最短路径数从1 - > 3只有1,但我肯定有两种方法,如前所述.

这是算法的实现:

 //count[][] is initialized with a 0 if no path between [u][v], and 1 at [u][v] if there is a weight at [u][v]. 

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    counts[i][j] = 1;
                }
                else if (dist[i][j] == dist[i][k] + dist[k][j] && k != i && k != j){
                    counts[i][j] ++;                
                }
            }
        }
    }

我基本上从维基百科页面复制/粘贴代码并进行修改以保持计数.

更新:我应该提到我为所有顶点获得了正确的最短长度,并且对于所有顶点我得到的正确计数除了[1] [3].

打印输出全部输出:

// Shortest paths              // counts
    1    2    3    4               1    2    3    4    
1   0    3    5    2           1   1    1    1    1
2   i    0    2    8           2   0    1    1    1      
3   i    7    0    6           3   0    2    1    1 
4   i    1    3    0           4   0    1    2    1

更新:逐行逐步执行代码,当k = 4,i = 1,j = 3时,我们找到权重5的1-> 3的最短路径.

更新:阅读Floyd-Warshall算法的维基百科条目,我收集到当k = 4时,我们正在检查通过顶点{1,2,3,4}的路径.但是,在k的每次迭代中,我们只会查看[1] [3]一次.我想也许这就是问题所在.

Answer 1

如果您使用二维 int 数组来存储数据，最好将双循环更改为从 0 运行到 N-1 以避免任何潜在的错误。我这样做了，结果是正确的（从 1->3 的最短距离是 5）。这是更新后的代码和打印输出：

     //count[][] is initialized with a 0 if no path between [u][v], and 1 at [u][v] if there is a weight at [u][v]. 
    int N = 4;
    int max = 1000000;
    int[][] dist = new int[N][N];
    int[][] counts = new int[N][N];
    dist[0][0] = 0;         dist[0][1] = max;   dist[0][2] = 8;     dist[0][3] = 2;
    dist[1][0] = max;       dist[1][1] = 0;     dist[1][2] = 2;     dist[1][3] = max;
    dist[2][0] = max;       dist[2][1] = 7;     dist[2][2] = 0;     dist[2][3] = 6;
    dist[3][0] = max;       dist[3][1] = 1;     dist[3][2] = 3;     dist[3][3] = 0;
    //initialize counts
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            if (dist[i][j]<max){
                counts[i][j]=1;
            }
        }
    }
    for (int k = 0; k < N; k++){
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    counts[i][j] = 1;
                }
                else if (dist[i][j] == dist[i][k] + dist[k][j] && k != i && k != j){
                    counts[i][j] ++;                
                }
            }
        }
    }
    System.out.println("i  1 2 3 4");
    for (int i=0; i<N; i++){
        System.out.print(i+1 + ": ");
        for (int j=0; j<N; j++){
            System.out.print(dist[i][j]>=max ? "i ":dist[i][j] + " ");
        }
        System.out.println();
    }
    System.out.println();
    System.out.println("i  1 2 3 4");
    for (int i=0; i<N; i++){
        System.out.print(i+1 + ": ");
        for (int j=0; j<N; j++){
            System.out.print(counts[i][j] + " ");
        }
        System.out.println();
    }

打印输出： i 1 2 3 4 1: 0 3 5 2 2: i 0 2 8 3: i 7 0 6 4: i 1 3 0

我 1 2 3 4 1: 1 1 1 1 2: 0 1 1 1 3: 0 2 1 1 4: 0 1 2 1