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

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

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

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

要有效地实现它，请在此处检查我的答案：更改 FloodFill 算法以获取两个数据点的 Voronoi 领土？ - 当我说时标记，你用你来的位置上的数字标记+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 可能会获胜。

Answer 2

您可能会被误导。 Dijkstra 算法存在不同的变体。计算从每个点到其他每个点的最短路径（如弗洛伊德的点）。

然而，典型的 Dijkstra 算法基于优先级队列，仅计算您所需的最短路径。它在执行过程中确实构造了几条路径，但这些都是从 A 到可能位于最终解决方案路径上的其他一些节点的部分路径。

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

Answer 3

使用A Star (A*) 算法。

Answer 4

如果您的移动受到足够的限制（例如，您只能向右、向上或对角线向上和向右移动），那么您可以利用其重叠子问题和次优子结构性质并使用 动态编程。

Answer 5

我不明白的是，如果你想要A和B之间的最短路径，你是否还需要查看A到C和A到D如果 C和D指向B？最短路径很可能是 ACB 或 ADB。您只需要扔掉未连接的节点即可。在我的一个项目中，我选取了 A 点和 B 点，检查其他点是否相连，以及那些没有相连的点从整个图表中删除。然后我继续使用 Dijkstra 算法。

Answer 6

你的网格形成了一个图表（或者至少可以被视为一个图表）。消除一些运动方向表明它是一个有向图。如果您根本无法从一个节点移动到另一个节点，则说明图中不存在一条边。

一旦您将网格编码为图形形式，就可以在众所周知的图形算法（您显然已经知道）中进行选择以遍历它以获得您想要的结果类型（例如最短路径）。

编辑：我已经查看了您发布的答案，但我不确定该代码应该是什么/做什么。例如，它有：if(y>=0) max(abs(x),y);。这似乎（至少对我来说）没有多大意义——max 的结果被简单地丢弃了。为了完成一些有用的事情，需要将其返回或分配或按该顺序进行某些操作。就目前情况而言，您所能希望的最好结果就是编译器将其识别为死代码，并且不会为其生成任何内容。

我的猜测是，代码并没有真正按照预期工作，即使它做了任何有用的事情，也更多是出于偶然而不是设计。需要花费相当多的时间和精力才能确保您已经解决了这样的问题，以至于您真正确定它做了什么，甚至更难以猜测它的真正意图。

Answer 7

下面是使用 BFS 实现矩阵中从 (0,0) 到 (0,m-1) 的最短路径的 Python 实现。您可以更改它以适应变量点。

n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
    curr=q[0]
    rem=q.pop(0)
    vis[curr]=True
    r=curr[0]
    c=curr[1]
    if r-1>=0 and arr[r-1][c]==0:
        if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
            q.append((r-1,c))
            x[r-1][c]=x[r][c]+1
    if r+1<n and arr[r+1][c]==0:
        if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
            q.append((r+1,c))
            x[r+1][c]=x[r][c]+1
    if c-1>=0 and arr[r][c-1]==0:
        if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
            q.append((r,c-1))
            x[r][c-1]=x[r][c]+1
    if c+1<m and arr[r][c+1]==0:
        if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
            q.append((r,c+1))
            x[r][c+1]=x[r][c]+1
    #for i in x:
        #print(i)
ans=x[0][m-1]
if ans==-1:
    print(-1)
else:
    print(ans)

• 输入矩阵应由 0 和 1 组成。 0 表示可能的移动。
• n 是行数。
• m 是列数。
• arr 是给定的矩阵。
• x 是距 (0,0) 的距离矩阵。
• vis 是一个字典，如果节点被访问，则给出布尔值。
• -1 的输出表明不存在这样的路径。

Answer 8

使用 A* 算法查找 2D 网格中两点之间的路径。
http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html