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

  • Z时代
  • 2024-01-10
  • 分类：问答

我知道有很多算法可用于计算图形或网格中两点之间的路径" title="最短路径">最短路径，例如广度优先的全对（Floyd’s），Dijkstra的。

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

我的问题是：

如果我有一个网格，即一个二维数组，并且我有兴趣计算两个点（例如P1和P2）之间的最短路径，并且我在网格上的移动方式是否受到限制（例如仅对角线，或者仅对角线和向上等），什么算法可以计算出来？

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

好的家伙，我在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);
}
};

回答：

Lee的算法：http :

//en.wikipedia.org/wiki/Lee_algorithm

本质上是BF搜索，下面是一个示例：http : //www.oop.rwth-aachen.de/documents/oop-2007/sss-

oop-2007.pdf

例如，如果您有一个网格，其中* =障碍物，则可以向上，向下，向左和向右移动，并且从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可能会获胜。

以上是 如何计算网格中两点之间的最短路径 的全部内容， 来源链接： utcz.com/qa/397428.html

回到顶部