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

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.

我知道有很多算法可以用来计算图或网格中两点之间的最短路径，比如宽度优先、全对(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?

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

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.

请注意，如果你有答案，我希望你发布算法的名称而不是算法本身(当然，如果你也发布算法的话会更好);例如，无论是Dijkstra的算法，还是Floyd的算法，或者其他什么。

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?

我在TOPCODER上找到了这个算法。在网格中你只能移动(对角线和向上)但是我不知道这是什么算法有人知道吗?

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

8 个解决方案

#1

Lee's algorithm: http://en.wikipedia.org/wiki/Lee_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

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

To implement it effectively, check my answer here: Change FloodFill-Algorithm to get Voronoi Territory for two data points? - when I say mark, you mark it with the number on the position you came from + 1.

为了有效地实现它，请检查我这里的答案:更改洪泛填充算法以获取两个数据点的Voronoi区域?-当我说mark的时候，你用从+ 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:

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

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

You put S in your queue, then "expand" it:

你把S放在你的队列中，然后“展开”它:

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.

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

#2

Use the A Star (A*) algorithm.

使用A*算法。

#3

You may be disinformed. There exist different variants of Dijkstra's algorithm. One computes the shortest paths from each point to every other point (like Floyd's).

你可能disinformed。Dijkstra算法有不同的变体。一个计算从每个点到其他点的最短路径(如Floyd)。

However, the typical Dijkstra algorithm is based on a priority queue and only computes your required shortest path. It does construct several paths during its execution, but those are all partial paths from A to some other nodes that might be on the final solution path.

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

Hence, you can easily interpret your grid as a graph (the restrictions like diagonals can then be taken into account accordingly) and run a Dijkstra search for the shortest path from A to B on that. It's really just a matter of modelling your problem, not that you need some fancy algorithm.

因此，您可以很容易地将您的网格解释为一个图(然后可以考虑对角线这样的限制)，并在这个图上运行Dijkstra搜索从a到B的最短路径。这只是对问题建模的问题，而不是你需要一些复杂的算法。

#4

If your movement is restrictive enough (e.g. you can only move to the right, or up, or to the diagonal up and right), then you can exploit its overlapping subproblems and suboptimal substructure nature and use dynamic programming.

如果你的移动有足够的限制(例如，你只能向右移动，或者向上移动，或者向对角线向上和向右移动)，那么你可以利用它重叠的子问题和次优的子结构性质，并使用动态编程。

#5

What I fail to understand is, if you want the shortest path between A and B, don't you still need to look at A to C and A to D if C and D point to B? Your shortest path could very well be A-C-B or A-D-B. You just need to throw out unconnected nodes. In one of my projects, I took points A and B, checked to see what other points were connected, and those that weren't were deleted from the entire graph. Then I proceeded with using Dijkstra's algorithm.

我不明白的是，如果你想要A和B之间的最短路径，难道你不需要看A到C和A到D如果C和D指向B?你的最短路径很可能是A-C-B或A-D-B。您只需要抛出未连接的节点。在我的一个项目中，我取点A和点B，检查其他点之间是否有联系，那些没有被从整个图中删除的点。然后我继续使用Dijkstra算法。

#6

Here's a python implementation of shortest path in a matrix from (0,0) to (0,m-1) using BFS. You can change it to fit variable points.

这是一个python实现，使用BFS实现从(0,0)到(0,m-1)的矩阵中的最短路径。你可以改变它以适应可变点。

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)

input matrix should consist of 0's and 1's. 0 is for possible movement.
输入矩阵应该由0和1组成。0表示可能的移动。
n is number of rows .
n是行数。
m is number of columns.
m是列数。
arr is the given matrix.
arr是给定的矩阵。
x is the distance matrix from (0,0).
x是距离(0,0)的距离矩阵。
vis is a dictionary giving a boolean if the node is visited.
vis是一个字典，在访问节点时给出一个布尔值。
output of -1 shows that there is no such path possible.
输出-1表示不存在这样的路径。

#7

Your grid forms a graph (or at least can be viewed as a graph). Eliminating some directions of movement indicates that it's a directed graph. If you can't move from one node to another at all, that's an edge that isn't present in the graph.

您的网格形成了一个图形(或者至少可以看作是图形)。去掉一些运动方向表明它是有向图。如果你不能从一个节点移动到另一个节点，那么这条边就不在图中了。

Once you've encoded your grid into graph form, it's a simple matter of selecting among the well-known graph algorithms (of which you're apparently already aware) to traverse it for the type of result you want (e.g. shortest path).

一旦你将你的网格编码成图的形式，你只需在已知的图算法中(显然你已经知道了)选择你想要的结果类型(例如最短路径)。

Edit: I've looked at the answer you posted, but I'm not sure what that code is supposed to be/do. Just for example, it has: if(y>=0) max(abs(x),y);. This doesn't seem (at least to me) to make much sense -- the result from the max is simply thrown away. To accomplish something useful, it needs to be returned or assigned or something on that order. As it stands, the best you can hope is that the compiler spots it as dead code, and doesn't generate anything for it.

编辑:我已经看了你发布的答案，但我不确定这段代码应该是什么。例如，它有:if(y>=0) max(abs(x)，y);这似乎(至少对我来说)没有多大意义——最大值的结果被轻易地抛弃了。为了完成一些有用的事情，它需要被返回或分配，或者按照这个顺序执行。就目前的情况而言，最好的结果是编译器发现它是死代码，并且不会为它生成任何东西。

My guess is that the code doesn't really work quite as intended, and if it does anything useful, it's more by accident than design. It would take a fair amount of time and effort to be sure you've sorted out problems like this to the point that you were really sure what it did, and even more difficult to guess what was really intended.

我的猜测是，代码并没有按照预期的那样工作，如果它做了什么有用的事情，它更多的是偶然而不是设计。你需要花费大量的时间和精力来确定你已经解决了像这样的问题，以至于你真的很确定它做了什么，甚至更难猜到它真正的意图是什么。

#8

-1

use A* algorithm for finding the path between two points in a 2D grid. http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

使用*算法在二维网格中找到两点之间的路径。http://theory.stanford.edu/ amitp / GameProgramming / ImplementationNotes.html

#1