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

我正在收集弗洛伊德沃尔斯发现的最短路径.对于此特定图表,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]一次.我想也许这就是问题所在.