Floyd Warshall Algorithm

general
, ,
1

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
2

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.

3

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.

4

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
5

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
6

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.

7

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

8

Thank you sir for your response.