Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shortest path problem with multiple goals on a grid

  1. Jan 5, 2013 #1
    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. jcsd
  3. Jan 5, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

  4. Jan 6, 2013 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook