# Floyd Warshall Algorithm

In Floyd Warshall Algorithm, we take three loops.

``````for k in 1 to number of vertices{
for i in 1 to number of vertices{
for j in 1 to number f vertices{
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
``````

I understood the above part and also why we do like that
But I did a little experiment and interchanged the places of (for loop of i) and (for loop of k)
and then checked but the answers remained same.I also interchanged (loop of k) and (loop of j),
still the answers come out to be same.

I couldn’t prove that the answer should be same. If the above interchanges aren’t same ,please tell me the case where the error will occur or if the above interchanges are same then please prove it.

3 Likes

Since all the 3 loops are starting and ending with same no i.e 1 to (no. of vertices)
so it doesn’t matter where u place them.It’s simple a matter of variable’s name.

But doesn’t it matter to update the dist[i][j] with already updated elements that is (dist[i][k]+dist[k][j]) rather than updating it with some value that is not itself updated.

If i understood your question correctly, This will be a counter example

consider following data

5 nodes and 5 bidirectional edges.

From To Cost

``````1 2 10
3 2 13
1 5 3
5 4 2
4 3 1
``````

Run in the order K I J

Dist[1][3] = 6

1->5->4->3

Run in order I J K

Dist[1][3] = 23

Reason : Consider state at I = 1, J = 3

K = 1 , No change

K = 2 , [1,2] + [1,3] = 23 (current Least)

K = 3 , No change

K = 4 , [1,4] + [4,3] but [1,4] is not yet calculated as it will come at state I = 1, J = 4

So here is the error!

2 Likes

At first you should mention how array `dist` is initialized and what graphs you consider.

Let’s assume that the graph is directed and initially
dist[i][i] = 0,
dist[i][j] = INF if there is no edge from i to j,
dist[i][j] is the length of the edge from i to j if the edge exists.

Using order `i, j, k` is definitely wrong.
For example, when you calculate `dist[1][2]` you use only initial values for `dist[1][k]` and `dist[k][2]` and it is even possible that `dist[1][2]` will remain `INF` after all calculations while there is a path from 1 to 2. Indeed, let the only edges in the graph be:
`dist[1][4] = 1, dist[4][3] = 1, dist[3][2] = 1`
So `dist[i][j] = INF` for all `i``j` other than these 3 pairs.

Clearly `dist[1][2] = 3` but using only
`dist[1][2] = min(dist[1][2],dist[1][k]+dist[k][2])`
for all `k` from `1` to `4` we will have `dist[1][2] = INF` in the end.

The same example fails order `i, k, j`.
The reason is that `dist[1][2] = dist[1][3] = INF` initially so when we loop over k for i=1 we do nothing for k=1,2,3 and when reach `k=4` we have `dist[4][2] = INF` so `dist[1][2]` remain INF and will be not updated anymore. Proof

Similarly the graph having only edges:
`dist[1][3] = 1, dist[3][4] = 1, dist[4][2] = 1`
will fail order `j, k, i`. Proof

So the only correct orders are `k, i, j` and `k, j, i` which are basically the same.

3 Likes

Thanks sir, such a test was hitting inside my mind, that’s why I posted here, but I couldn’t generate the test case that well as you did.
Besides will your explanation also be true for undirected graphs. As the coach Rus Coxx say that we shouldn’t use Floyd Warshal for directed graphs,I don’t know why he say that.

I don’t know who is Rus Coxx but Floyd-Warshall was designed exactly for directed graphs.
Undirected graph is a partial case of directed graph where dist[i][j]=dist[j][i] for all i,j.

The same example fails the undirected version. Proof

Thank you sir for your response.

//