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

There is a problem with the algorithm you've come up with. Not the code. Your updates suggest that you had been closing in on it.

You have 2 shortest paths to get from 4 to 3: 4-->3 and 4-->2-->3. Both are of length 3 (something that your algorithm will have established by the time k is incremented to 4). So in the final iteration when k = 4, your program will ask, will the path from 1 to 3 be shorter if I go via 4? Then it will decide Is 8 > 2+3 - Yes! And you'll set the number shortest paths to 1. But there were 2 sub-paths from 4 to 3 that you won't be considering again.

This is because the Floyd Warshall only considers one vertex (k) at time and checks if the paths are shortened by going via that point. So your program only counts the number of shortest paths with different second last vertices (the ones just before the destination). It does not take into account the fact that to even get to the second last point, you had 2 shortest paths available.

The following example should make it clear:

How many paths are there for you to reach the base (bottom most point) in the graph shaped as a "V". Your program will correctly look at the base at say 2. But when asked about a graph shaped as a "Y", your program will once again look at the base and incorrectly conclude that only one path leads to the base.

You are lucky that the test case you chose caught this problem!

Unfortunately, I don't think a minor edit would fix it. This is because the Floyd Warshall algorithm guarantees a shortest path between all pairs. Not all shortest paths between all pairs. But if you're only interested the paths this algorithm finds, instead of initializing the counts to 1 and incrementing them by 1, initialize and increment by the number of shortest sub-paths that have already been found for the vertex you're going via. (2 in this particular case).

Answer 2

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