algorithm - 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.