Floyd warshall implementation appears to be missing a shortest path

Question

I'm collecting a count of the shortest paths that floyd warshall finds. For this particular graph the shortest path for 1 -> 3 is 5, and there are two paths with this weight: 1->4->2->3, and 1->4->3.

I wasn't sure the best way to display the graph, so I'm going to use a matrix, please feel free to suggest another way if you know of a better alternative.

 //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

So when I run my code, I'm getting the count of shortest paths from 1 -> 3 as just 1, but there are most certainly 2 ways as I mentioned before.

Here is the implementation of the algorithm:

 //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] ++;                
                }
            }
        }
    }

I basically copy/pasted the code from the wikipedia page and modified to keep the count.

Update: I should mention that I am getting the correct shortest length for all vertices, and for all of them I'm getting the correct count except for [1][3].

Printout of full output:

// 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

Update: Stepping through the code line by line, we find a shortest path from 1->3 of weight 5 when k = 4, i = 1, j = 3.

Update: Reading the wikipedia entry for the Floyd-Warshall algorithm, I've gathered that when k = 4, we are checking for paths going through the vertices {1, 2, 3, 4}. However, in every iteration of k we will only look at [1][3] only once. I think maybe this is the problem.

Answer 1

If you are using a two dimensional int array to store your data, it would be best to change your double loop to run from 0 to N-1 to avoid any potential errors. I did that and the results are correct (shortest distance from 1->3 is 5). Here is the updated code and printout:

     //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();
    }

Printout: 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

i 1 2 3 4 1: 1 1 1 1 2: 0 1 1 1 3: 0 2 1 1 4: 0 1 2 1