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
      ^