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

2018-06-22 15:08:35

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

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

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

请注意，如果您有答案，我希望您发布算法的名称而不是算法本身（当然，如果您也发布算法，则更好）。 例如，无论是Dijkstra算法还是Floyd's，或者其他什么。

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

okey家伙我发现这个算法在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);
}
};

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

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

为了有效地实现它，请查看我的答案：更改FloodFill-Algorithm以获得两个数据点的Voronoi Territory？ - 当我说分数时，你用你来自+1的位置上的数字来标记它。

例如，如果你有这个网格，那里有一个* =障碍物，你可以向上，向下，向左和向右移动，并且你从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可能会赢。

使用星号（A *）算法。

你可能会被解雇。 Dijkstra算法存在不同的变体。计算每个点到其他点的最短路径（如Floyd's）。

但是，典型的Dijkstra算法基于优先级队列，只计算所需的最短路径。它在执行过程中会构建若干路径，但这些路径都是从A到其他可能位于最终解决方案路径上的其他节点的部分路径。

因此，您可以轻松地将您的网格解释为图形（然后可以相应地考虑对角线等限制），然后运行Dijkstra搜索从A到B的最短路径。这只是一个建模问题的问题，而不是你需要一些花哨的算法。

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

上一篇: How to calculate the shortest path between two points in a grid

下一篇: Good algorithm for finding the diameter of a (sparse) graph?