Floyd-Warshall Algorithm

general
1

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?

2

Are you sure your latex formula is correct?

3

you can see lecture of MIT or cormen

4

here’s the MIT lecture notes: Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare

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

5

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

6

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.

7

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

8

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

9

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

10

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: Floyd Warshall Algorithm | DP-16 - GeeksforGeeks

1 Like
11

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.

12

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.

13

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

14

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
15

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.

16

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

17

means , why similar reason?

18

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