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

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, ie 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);
}
};

---

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.

---

使用星号（A *）算法。

---

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.

链接地址: http://www.djcxy.com/p/63498.html

上一篇: 如何在图中找到确切长度的路径

下一篇: 如何计算网格中两点之间的最短路径