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

Question

Hello!

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!

Answer 1

A Star (A*)

Answer 2

You may be disinformed. There exist different variants of Dijkstra's algorithm. One computes the shortest paths from each point to every other point (like Floyd's).

However, the typical Dijkstra algorithm is based on a priority queue and only computes your required shortest path. It does construct several paths during its execution, but those are all partial paths from A to some other nodes that might be on the final solution path.

Hence, you can easily interpret your grid as a graph (the restrictions like diagonals can then be taken into account accordingly) and run a Dijkstra search for the shortest path from A to B on that. It's really just a matter of modelling your problem, not that you need some fancy algorithm.

Answer 3

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 4

What I fail to understand is, if you want the shortest path between A and B, don't you still need to look at A to C and A to D if C and D point to B? Your shortest path could very well be A-C-B or A-D-B. You just need to throw out unconnected nodes. In one of my projects, I took points A and B, checked to see what other points were connected, and those that weren't were deleted from the entire graph. Then I proceeded with using Dijkstra's algorithm.

Answer 5

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: http://stackoverflow.com/questions/2288830/change-floodfill-algorithm-to-get-voronoi-territory-for-two-data-points/2288898#2288898 - 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.

Answer 6

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 7

Your grid forms a graph (or at least can be viewed as a graph). Eliminating some directions of movement indicates that it's a directed graph. If you can't move from one node to another at all, that's an edge that isn't present in the graph.

Once you've encoded your grid into graph form, it's a simple matter of selecting among the well-known graph algorithms (of which you're apparently already aware) to traverse it for the type of result you want (e.g. shortest path).

Edit: I've looked at the answer you posted, but I'm not sure what that code is supposed to be/do. Just for example, it has: if(y>=0) max(abs(x),y);. This doesn't seem (at least to me) to make much sense -- the result from the max is simply thrown away. To accomplish something useful, it needs to be returned or assigned or something on that order. As it stands, the best you can hope is that the compiler spots it as dead code, and doesn't generate anything for it.

My guess is that the code doesn't really work quite as intended, and if it does anything useful, it's more by accident than design. It would take a fair amount of time and effort to be sure you've sorted out problems like this to the point that you were really sure what it did, and even more difficult to guess what was really intended.