How to implement the shortest path algorithm in this scenario?

Question

In my assignment I have a MxN grid

e.g.

M = 5, N = 8

KKKK....
.###...X
.XX#...X
...#....
........

K - start point, X - finish point, # - obstacle

I need to find the smallest number of moves to carry packages from start points to finish points. We can only carry 1 package at a time and we can't move diagonally.

The answer for this example is 20.

My suggestion would be to implement A* algorithm and launch it for every possibility (calculate the smallest number of moves from each of the start points to each of the end points) and the pick the smallest one, considering the fact that 1 package covers 1 end point.

Is there a better way to implement that?

Answer 1

Although my practical understanding of it is limited, I'll attempt to formulate the problem as a minimum-cost flow problem. Consider each starting point a source and each finish point a sink. The cost of sending a flow, f, over a particular edge is f * a, where a is the edge's cost. A customary way to handle multiple sources and sinks is to connect each group to another single instance.

Tentative formulation:

Call n the number of starting points or finish points.

1. connect all starting points to a single source with flow n, where each edge has capacity and flow 1 and cost 0.

2. connect all finish points to a sink with each edge having capacity 1 and cost 0.

3. all other edges have infinite capacity (at least n seems to cover that) and cost 1.

4. find min cost for achieving flow n through the network.

Diagram:

imaginary source
 with edge to each
  S with capacity 1
 / /|\
S1S-S1S2.2.2.2.
2       | | | 2   imaginary sink
. # # # .-.-.-T -- with edge to
2       | | | 1     each T with
.2T1T # .-.-.-T --  capacity 1
                      |   |
. . . # . . . .

. . . . . . . .

(Numbers in the diagram are the optimal flow through each edge, they add up to 20.)