How to calculate the shortest path between two poi

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

If your movement is restrictive enough (e.g. you can only move to the right, or up, or to the diagonal up and right), then you can exploit its overlapping subproblems and suboptimal substructure nature and use dynamic programming.

Answer 2

Use the A Star (A*) algorithm.