0

I am designing a system to find shortest route covering least number of cells. Suppose the plane is divided into rectangular cells. What will be the best suited algorithm for this. I am just looking for the head-start and not the proper code or implementation.

Rajat Saxena
  • 3,834
  • 5
  • 45
  • 63

1 Answers1

2

You are dealing with shortest path problem, in an unweighted graph (vertices are the cells in your grid, and edges are possible moves from one cell to the other)

  • The simplest approach is a simple BFS - that finds the shortest path from a source to all targets (in unweighted graphs).
    This algorithm is fairly simple and is iteratively "discovering" the closest nodes, all nodes of distance 1, then of distance 2, ....
  • An optimization is using a bi-directional search. Here you can take advantage of having single source and single target by doing BFS from both sides, effectively reducing the number of nodes you need to develop dratically.
  • One more optimization could be to use A* Search Algorithm with an admissible heuristic function, such as manhattan distances.
    In A* Search, you take advantage that the graph is not some arbitrary graph - but a grid, and you can estimate distance from one node to the other, based on their locations on the grid. The algorithm will uses these estimations to find the optimal path quicker.

Note - all algorithms I suggested find the shortest path, difference is in the time it will take them to find it.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • You know how "hyperlocal delivery" websites work, so I guess it's okay if the sites take a few minutes to find shortest routes – Rajat Saxena Jun 29 '15 at 09:29