Does Floyd–Warshall work on all graphs?

Question

Floyd–Warshall calculates minimum distance between any two vertices in the graph.

for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}

So, it basically calculates distance between every two nodes i,j having 1 intermediate node in the shortest path, then having 2 intermediate nodes in the shortest path and so on until there are N intermediate nodes in the shortest path.

So, basically this algorithm uses the previous computed distances to compute the new shortest distances.

But, for a graph like 0->2->3->1. It wouldn't be able to compute the shortest between 0 and 1 because in starting it doesn't know the shortest distances from 0 to 3 or 2 to 1 in the distance matrix.

In dynamic algorithms, we start from shorter problems and then use them to compute solution to larger problems. But, here we don't know which one are our shorter problems.

So, how are we able to use this algorithm here?

Answer 1

The way to answer this kind of question is to simulate the algorithm with pencil and paper to see what it actually does.

Initially, we have dist[i][i] = 0 for all i, dist[0][2] = dist[2][3] = dist[3][1] = 1 and every other entry is infinite.

When we consider k = 0, nothing changes, since dist[i][k] = ∞ for all i except i = 0.

When we consider k = 1, nothing changes, since dist[k][j] = ∞ for all j except j = 1.

When we consider k = 2, we have dist[0][2] + dist[2][3] = 2 < dist[0,3] = ∞, so we set dist[0,3] = 2; nothing else changes.

When we consider k = 3, we have dist[0][3] + dist[3][1] = 3 < dist[0,1] = ∞, so we set dist[0,1] = 3; nothing else changes.

So the algorithm has correctly computed the shortest path from 0 to 1.

The point is that we're not really using dynamic programming based on the length of the intermediate path but on the highest-numbered vertex along that path. Suppose you want to compute the shortest path from a to b. That path must pass through some highest-numbered vertex – call it c. Because that's the highest-numbered vertex on the path, we know that all the vertices on the paths a-c and c-b have lower numbers. So, in particular, by the time we reach the k = c iteration of the outer loop, we've already calculated all shortest paths between all vertices that use only vertices 0...c-1 as intermediate vertices. And that's enough information to calculate the shortest paths a-c and c-b and, hence, the shortest path a-b.