Algorithm for finding the best route from single source to multiple destinations in a matrix

Question

Problem statement: We have an m * n matrix. The starting point is the top left cell. We can only go down or right in the matrix. Destinations are randomly chosen in the matrix. Now we need to find the best routine with the following constraints:

1. Each node on the route could only have one parent node but could have at most two child nodes.
2. minimize duplication routes. For example, if we have destinations look like below:

Instead of using the routine on the left-hand side, we should reduce it to the right-hand side one.

3. prefer going right then down unless going down is shorter than right.

In the example below, instead of choosing the left hand side solution, we should prefer right hand side one as it branches to (2, 1) down by move down from (2, 0) by 1 instead of going right by 2 from (0, 1).

Other examples look like below, which are all best routines.

I'm working on this for a while. I've looked into some algorithms like transitive reduction and Dijkstra, but didn't figure them out. If you would like to give me some hint on algorithms that I could look into that would be great.

Thanks!

---

Edit 2:

I've received some ideas about Dijkstra algorithm and using dynamic programming. I think for Dijkstra algorithm if you could provide hints for converting this problem to a graph problem that would be great. I was looking into the algorithm and think the primary issue of it is that cells do not have to be visited. In the example below, if we remove one of the destinations, the whole routine would have a significant change comparing to the left-hand side map.

For dynamic programming, I have a thought on how a node should join to the path. The priority should look like:

But the problem is it fails to consider the problem with a dynamic view, which will output a wrong result.

Answer 1

I think your examples could all fit with the following general algorithm: traversing left and up simultaneously — starting with the ends of the first row and column, followed by the ends of the second row and column, etc. — extend routes from each D encountered to the closest route, D or S (Manhattan distance in the N-NW-W arc, of course).

Example 7:

  1 2 3 4
1 S     D

2     D

3   D

4 D     D

  1 2 3 4
1 S-----D<
  |
2 |   D
  |
3 | D
  |
4 D     D
  ^

  1 2 3 4
1 S-----D
  |   |
2 |   D  <
  |
3 |-D
  |
4 D     D
    ^

  1 2 3 4
1 S-----D
  |   |
2 |   D
  |
3 |-D
  |
4 D-----D<
        ^

Example 5:

  1 2 3 4
1 S

2       D

3     D

4 D     D

  1 2 3 4
1 S      <
  |
2 |     D
  |
3 |   D
  |
4 D     D
  ^

  1 2 3 4
1 S
  |
2 |-----D<
  |
3 |   D
  |
4 D     D
    ^

  1 2 3 4
1 S
  |
2 |-----D
  |   |
3 |   D  <
  |
4 D     D
      ^

  1 2 3 4
1 S
  |
2 |-----D
  |   |
3 |   D--
  |     |
4 D     D<
        ^

Example 1:

  1 2 3 4
1 S

2     D

3   D   D

4     D

  1 2 3 4
1 S--
    |
2   --D  <
    |
3   D   D

4     D
    ^

  1 2 3 4
1 S--
    |
2   --D
    |
3   D---D<
      |
4     D
      ^

Answer 2

This is a recursive problem. You should try practicing Greedy Algorithms and Dynamic Programming, and try some categorized followed by some mixed-bag programming questions to give you a better idea about what to apply when, and how to make algorithms that are a combination of the two.

Use a Divide and Conquer approach to solve this. put yourself in the place of the moving cursor, and think about an ordered set of logical actions that you could follow at each node so that you solve the problem.

I will add my algorithm to solve this problem after a few days. This is to ensure that I don't accidentally end up helping someone heat in a competition.

You could refer to this and this to get a little insight into the technique. I also found a fun article related to understanding recursion better. It might not be very informative, but it is definitely motivational.

Hint: There are only 3 possible places where an unvisited destination node could be located for it to be possible to visit:

1. It is directly below the current node
2. It is directly to the right of the current node
3. it is somewhere to the bottom-right side of the current node

A possible algorithm could be that you recursively:

1. check for a node below you, and visit it immediately via a recursive function call if present.
2. check for the farthest node present in the current horizontal level, and draw a path to it without a recursive call.

[edit 1 : Sorry, I forgot to mention the default case!!!]

3. If there is no node in the same horizontal or vertical of the cursor, move right. The algorithm may seem simple to look at but will solve the problem. Its complexity is also only O(N).

Answer 3

Thank you for all your answers and comments. All of the comments are valuable for me and stimulated my thinking.

I now come up with a solution that takes advantages of the existing Dijkstra algorithm and correct node traversing order. Instead of starting from top left corner, we now make the original source as destination. Then turns all directions backwards so that now we can only go left or up from a node. The solution looks like below:

1. Build a weighted graph. All going left edges have the weight of 1, all going up edges have the weight of (m + 1 - col), so that the first column of going up routines (with a 4 by 4 matrix) all have the weight of 5. Example weight graph looks like below:

2. Add node (0, 0) to founded routes.

3. Start from top left node (0, 0), check all the nodes on its right ((0, 0) to (0, n)). Then check all the nodes on its bottom ((1, 0) to (m, 0)). For all the Source node (originally destination node), use Dijkstra algorithm to find its shortest way back to the founded routes, add all nodes in Dijkstra algorithm to founded routes.

4. Repeat step 3 for all node (i, i) until the last one ((m, m) or (n, n)).

Any other more efficient solutions are highly welcome. Also, if you figured out a pitfall in this algorithm that would be great. This algorithm seems to work but my feeling is that it's not the most effective way.