algorithm - 如何计算网格中两点之间的最短路径

Question

我知道有许多算法可用于计算图形或网格中两点之间的最短路径，例如广度优先、全对(Floyd 算法)、Dijkstra 算法。

但是，正如我所注意到的，所有这些算法都计算该图形或网格中的所有路径，而不仅仅是我们感兴趣的两点之间的路径。

我的问题是:如果我有一个网格，即二维数组，并且我有兴趣计算两点之间的最短路径，比如 P1 和 P2，并且如果我在网格上移动的方式有限制(例如仅对角线，或仅对角线和向上等)，什么算法可以计算这个？

这里请注意，如果你有答案，我希望你贴出算法的名称而不是算法本身(当然，如果你也贴出算法就更好了)；例如，无论是 Dijkstra 算法、Floyd 算法还是其他算法。

请帮助我，我已经考虑了好几个月了!

---

伙计们，我在 TOPCODER.COM 上找到了这个算法在网格中，您只能移动(沿对角线和向上)但我无法理解这是什么算法，有人知道吗？

#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

李的算法:http://en.wikipedia.org/wiki/Lee_algorithm

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

要有效地实现它，请在此处查看我的答案:Change FloodFill-Algorithm to get Voronoi Territory for two data points? - 当我说标记时，你用你来自 + 1 的位置上的数字标记它。

例如，如果你有这个网格，其中 a * = 障碍物，你可以上下左右移动，你从 S 开始必须走到 D，0 = 自由位置:

S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

您将 S 放入您的队列中，然后“展开”它:

S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

然后展开它所有的邻居:

S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D

所有这些邻居的邻居:

S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D

以此类推，最后会得到:

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

所以从 S 到 D 的距离是 9。运行时间是 O(NM)，其中 N = 行数，M = 列数。我认为这是在网格上实现最简单的算法，而且在实践中也非常有效。它应该比经典的 dijkstra 更快，尽管如果您使用堆实现它，dijkstra 可能会胜出。