How to calculate the shortest path between two points in a grid

Question

I know that many algorithms are available for calculating the shortest path between two points in a graph or a grid, like breadth-first, all-pairs (Floyd's), Dijkstra's.

However, as I noticed, all of these algorithms compute all the paths in that graph or grid, not only those between the two points we are interested in.

MY QUESTION IS: if I have a grid, i.e. a two dimensional array, and I'm interested in computing the shortest path between two points, say P1 and P2, and if there are restrictions on the way I can move on the grid (for example only diagonally, or only diagonally and upwards, etc.), what algorithm can compute this?

Please notice here that if you have an answer, I would like you to post the name of the algorithm rather than the algorithm itself (of course, even better if you also post the algorithm); for example, whether it is Dijkstra's algorithm, or Floyd's, or whatever.

Please help me, I've been thinking about this for months!

---

okey guys i found this algorithm on TOPCODER.COM here in the grid you can move only (diagonally and up) but i can't understand what algorithm is this by any means could any one know?

#include<iostream> #include <cmath>  using namespace std;     inline int Calc(int x,int y)  {    if(abs(x)>=abs(y)) return abs(x); int z=(abs(x)+abs(y))/2; return z+abs(abs(x)-z);  }  class SliverDistance {       public: int minSteps(int x1,int y1, int x2, int y2) {     int ret=0;     if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;     return ret+Calc(x2-x1,y2-y1); } }; 

Answer 1

Lee's algorithm: http://en.wikipedia.org/wiki/Lee_algorithm

It's essentially a BF search, here's an example: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

To implement it effectively, check my answer here: Change FloodFill-Algorithm to get Voronoi Territory for two data points? - when I say mark, you mark it with the number on the position you came from + 1.

For example, if you have this grid, where a * = obstacle and you can move up, down, left and right, and you start from S and must go to D, and 0 = free position:

S 0 0 0 * * 0 * * 0 0 * 0 0 * * * 0 0 D 

You put S in your queue, then "expand" it:

S 1 0 0 * * 0 * * 0 0 * 0 0 * * * 0 0 D 

Then expand all of its neighbours:

S 1 2 0 * * 0 * * 0 0 * 0 0 * * * 0 0 D 

And all of those neighbours' neighbours:

S 1 2 3 * * 3 * * 0 0 * 0 0 * * * 0 0 D 

And so on, in the end you'll get:

S 1 2 3 * * 3 * * 5 4 * 7 6 * * * 7 8 9 

So the distance from S to D is 9. The running time is O(NM), where N = number of lines and M = number of columns. I think this is the easiest algorithm to implement on grids, and it's also very efficient in practice. It should be faster than a classical dijkstra, although dijkstra might win if you implement it using heaps.