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}

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

here’s the MIT lecture notes: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-19-shortest-paths-iii-all-pairs-shortest-paths-matrix-multiplication-floyd-warshall-johnson/lec19.pdf

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??

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