# Shortest path problem with multiple goals on a grid

1. Jan 5, 2013

### hddd123456789

Hi, I've been reading up a bit on the shortest path problem in graph theory and was wondering if the problem I'm trying to solve is a variation of the same graph theory problem.

Say you have a grid of vertices and edges representing aisles and cross-aisles in a warehouse. In a standard picking problem, you will have to go and pick items up in various locations throughout the warehouse.

The algorithm that I found is for single pair shortest path meaning that there is one source and one goal. Am I right in thinking that what I need is an algorithm that takes a single source with multiple goals (pick locations) and then finds the shortest path from the source that goes through all the goals? Is there such an algorithm?

2. Jan 5, 2013

3. Jan 6, 2013

### haruspex

It might be much more tractable than the general TSP. E.g. if a candidate solution has a step from node A to node B, and there is a node C within the rectangle with corners A. B, then you might as well visit C on the way from A to B.