Need help in DP approach

In some problems (like floyd warshall algorithm), we use three loops, i,j,k. But we use k first, and then nest i and j where i and j access the given array. What is the problem if we use k nested in j nested in i? (i>j>k)

Your question is somewhat ill-defines. Obviously you can name the variables in any way you like, so referring to them by name doesn’t really help. But I try to answer the question as I understand it.

You cant simple change the order, because they are completely different things. In the correct approach you are iterating over all nodes. For each node k you check whether the path between two nodes can be improved by going via k.
Changing the order amounts to a different thing. You are iterating over all pairs. For each pair you look at any node and whether you can improve the path via this node.

Think about a path from a to b with at least two nodes ( say c,d) in between. And assume that a and b are the first pair you check. Then you wont get any path between a an d b in the second approach because you’re at most checking one node in between.
In the first approach you arrive in the outer iteration either at c or at d. Say it’s c than you discover the path a-c-d . When you are checking node d later on You will discover the whole path because you already have a part of it.

1 Like

Thank you. That clears my doubt.

//