Recursion Help

Programming is hard, and it can be very frustrating. This has nothing to do with you in particular. Don't lose hope, friend.

This looks to me like a shortest-path problem. Here is one way to tackle this:

  1. The shortest path from a neighbour element e of the bottom right of the matrix D is e, followed by D. That is, the path e followed by D. Two elements.
  2. Given any other element e in our matrix, the shortest from e to the bottom right of the matrix is e, followed by the path with the lowest sum among all the shortest paths from each of the neighbours of e.

That sounds awfully complex, so let's see if I can visualize it.

First, think of a neighbour of the bottom right. In the example matrix, we have 2 neighbours:

1 20
4 25

20 and 4 are the only neighbours of the bottom right element, 25. The shortest path from 20 to 25 is 20->25. Not 20->1->4->25. :) That's what I mean in step 1 above. Similarly, the shortest path from 4 to the bottom right corner is 4->25.

This is the base of the recursion.

Now, for all other cases, given an element, say 2 surrounded by 8 neighbours,

2 3 44
7 2 9
1 5 14

the shortest path from that element is 2 followed by the path of the lowest sum. We find that path with lowest sum by computing the sum of each of the shortest paths among all of the neighbours, recursively. So, in the above example, compute the shortest path among all of the neighbours (a recursion call), and then sum app each of these paths, and then choose the path 2->p where p is the path with the lowest sum.

Does it make sense? Does it help?

This in recursion would make a slow algorithm, but it doesn't sound like the instructor cares about that.

/r/cpp_questions Thread