我知道许多算法可用于计算在一个图或网格两点之间的最短路径，如广度优先，全双（Floyd的），Dijkstra的

不过，正如我注意到，所有这些算法计算在图形或网格中所有的路径，而不是只有两点我们感兴趣的。

我的问题是：的 如果我有一个网格，即二维数组，我感兴趣的是计算两点之间的最短路径，称P1和P2，如果有在路上的限制，我可以在网格上移动（例如只对角，或只对角和向上，等）， 什么样的算法可以计算吗？

请注意在这里，如果你有一个答案，我想你张贴算法的名称，而不是算法本身（当然，甚至更好，如果你还发布了算法）;例如，无论是Dijkstra算法，或弗洛伊德的，或什么的。

请帮帮我，我一直在想着这几个月！

奥基家伙，我发现这个算法在顶部codeR.COM 这里的网格，只能移动（对角线及以上） 但我不明白的算法是这样的以任何方式可以任何人知道吗？

 ＃包括＆LT;的iostream＆GT;
＃包括＆LT; CMATH＆GT;

使用名字空间std;




内联INT计算（INT X，int y）对

{



如果（ABS（X）＆GT; = ABS（Y））返回ABS（X）;
INT Z =（ABS（x）的+ ABS（Y））/ 2;
返回Z + ABS（ABS（X）-Z）;
 }

类SliverDistance
{


    上市：
INT minSteps（INT X1，Y1 INT，INT×2，INT Y2）
{
    INT RET = 0;
    如果（（（X1 + Y1）及！1）=（（X 2 + Y）及1））Y1 ++沤++;
    返回RET +计算器（X2-X1，Y2，Y1）;
}
};
 

解决方案

利的算法： http://en.wikipedia.org/维基/ Lee_algorithm

这本质上是一个BF搜索，这里有一个例子：http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf

要有效地实现它，在这里检查我的答案是：http://stackoverflow.com/questions/2288830/change-floodfill-algorithm-to-get-voronoi-territory-for-two-data-points/2288898#2288898 - 当我说的标记，你与你来自+ 1的位置数将其标记

例如，如果你有这样的网格，其中* =障碍，你可以向上，下，左，右，并从S开头的，必须去D和0 =自由位置：

 秒0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
 

您把S在您的队列，然后展开吧：

 的1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
 

然后展开它的所有邻国：

 的1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
 

和所有邻居的邻居：

 的1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D
 

等等，最终你会得到：

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

所以从S到D中的距离是9的运行时间为O（NM），其中线的N =数量，M =列数。我认为这是实现对网格的最简单的算法，而且它也是非常有效的做法。它应该比一个经典的Dijkstra算法更快，但如果你使用堆实现它的Dijkstra可能会赢。

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

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.