# Floyd-Warshall Algorithm

I read from MIT lectures, that algorithm for all pair shortest path is
for m in range(1,n)
for u in V
for v in V
for x in V
if d_{uv}>d_{ux}+d_{xv}
d_{uv}=d_{ux}+d_{xv}

But in all other places algorithm is like

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

Plz explain me which one correct and why?

Are you sure your latex formula is correct?

you can see lecture of MIT or cormen

See page 17.Don’t know what resource you using tho.

ok, means i and j are inner for loop line, which checks the point with a point creating by k (which is an outer for loop point, right?)

yes, somewhat. Basically here what we are doing is that we are finding intermediate points between i and j. So, if i is the source and j is the destination. we check if k is an intermediate point between them or not.

If we are finding intermediate point, then why k is in outer for loop? Why k is not in innermost for loop??

because we pick intermediate points, one by one in i to j

I have not got. Can u plz elaborate a bit more? How to pick points by inner loop and how by outer loops??

Ok.
Imagine that you want to update all the pairs of nodes( that means i and j). and you need to check all the nodes, whether they are intermediate or not.
So, for k=1 to n gives us all the nodes
Now,for each ‘k’, we pick the pairs
for i=1 to n
for j=1 to n
And we check if k is included between this path.
That’s why for k=1 to n is an outer loop. because we keep on updating the shortest path between a pair of nodes.

Here’s a better explanation, if you still not got it: https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

1 Like

The extra “for m in range(1,n)” is used when there can be cycles with total negative weight. If there exists such a cycle, you can go around it as many times as you want and get a shortest path length -infinity.

Now you can show that if there is no negative weight cycle, then after at most n-1 iterations, there will be no update to the dp matrix but I am in no mood to explain that. You can probably read about them somewhere.

1 Like

Ok , u mean I and j first creating an edge. And then and then comes out and checking if k point already included or not. If not included then simply checks distance of I and j from point k. right??
PS: In geeks for geeks only code is given. If there some explanation is given with each line of code, it would be helpful to us.

Plz explain if possible. I shall be really helpful if get a good explanation.

i is source node, and j is the destination node. we need distance of i to j(shortest distance).

we check if distance(i to k)+distance(k to j) [Which means distance of i to j] is less than what we already have as the distance between i to j. this way we calculate the minimum distance.

1 Like

I just realized that I’ve been thinking of is the Bellman-Ford algorithm. Sorry about that. But I think you can use a similar reasoning to explain your problem too.

But still not understanding, why I and j is in innermost loop. What if it will be in outermost loop??

means , why similar reason?

We need k in the outermost loop because we need to see all the possibilities.We need to check the shortest distance between i to j n times.

1 Like