CODEWITHSUNDEEP
algorithmloops
Myang310
Myang310

Reputation: 63

Floyd-Warshall Algorithm - Why this order?

In the algorithm, you have 3 loops for shortest[u,v,x] which goes x from 1 - n, u from 1 - n, v from 1 - n.

Why are the loops from x,u,v and not x,v,u or u,v,x?

Upvotes: 0

Views: 544

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

Assuming (u,v) are indices for vertices and x denotes the index such that we are finding the shortest distance between vertex u and vertex v with only those vertices in between that are numbered <= x.

Hence the recurrence for dist[u,v,x] uses dist[u,v,x-1], dist[u,x,x-1] and dist[x,v,x-1].

Since there are three vertices involved (u,v,x) in the computation of dist[u,v,x], so we should have already computed dist's for all three pairs before computing dist[u,v,x].

So, the loop for x has to be the outer-most loop. Inner loop can be either v,u or u,v because both are vertices.

Upvotes: 2

Related Questions