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?

@Dementic This is language-agnostic, and OP suggests using a A* and launching it from every possibility which is a concrete solution proposal. — ggorlen
– ggorlen, Commented Jan 13, 2019 at 0:34
@Dementic No, language-agnostic algorithm questions are very much on topic for SO. — ggorlen
– ggorlen, Commented Jan 13, 2019 at 6:25
@ggorlen in this particular example the packages block each other. We can't move diagonally, and we don't have any free neighbours in this case — MarJan
– MarJan, Commented Jan 13, 2019 at 9:46
@Richard, my guess is that it will be tested for sth like 100x100 with 10-20 start spots max — MarJan
– MarJan, Commented Jan 13, 2019 at 12:05

גלעד ברקן · Accepted Answer · 2019-01-13 21:01:40Z

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.

connect all starting points to a single source with flow n, where each edge has capacity and flow 1 and cost 0.
connect all finish points to a sink with each edge having capacity 1 and cost 0.
all other edges have infinite capacity (at least n seems to cover that) and cost 1.
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.)

edited Jan 13, 2019 at 21:01

answered Jan 13, 2019 at 13:42

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

MarJan Over a year ago

could you give me a practical example? since I can't really understand your diagram correctly. Pipes connect the start point and sinks, but what are "2" for?

גלעד ברקן Over a year ago

@MarJan the numbers in the diagram are the optimal flow through each edge (they add up to 20). An edge in the problem is any single allowed move. (I drew edges as lines where there was no expected flow.) Does that make sense?

MarJan Over a year ago

it does make sense, thanks for the clarification. Will try to implement it that way vs A*. Will compare them and then choose the better one. Thank You :)

MarJan Over a year ago

so my Maximum Flow should be equal n, where n is the number of Start/End Points?

גלעד ברקן Over a year ago

@MarJan in the example, it seems to me the flow that's achieved is n = 4 (number of starting or ending points), since 4 gets from the source to the sink.

|

Collectives™ on Stack Overflow

How to implement the shortest path algorithm in this scenario?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related