如何在具有多个端点的二维数组中找到最短路径？

Question

我有一个程序可以创建一个类似于此的二维数组：

X X X X X X X B X X
B X X X X X X X X X
B X X X X X X X X X
X X X X X X X B X X
X X X X X O B X X X
B X X X X X B X X X
X X X X X X X X X X
X X X X X X X X X X

X = 空闲空间可自由漫游

B = 无法自由漫游的阻塞区域

O = 正在移动的对象

我想帮助弄清楚如何找到通往任何端点的最短路径。通常我会使用 Dijkstra 算法，但是我有多个要考虑的点，而不是 1 个点。物体的点正在到达边缘，我想在那里找到最短的路径。

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-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 可能会赢。

对任何起点和终点执行此操作，并在您的情况下选择具有最小整数的终点。