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

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 = 空 space 自由漫游

B = 无法自由漫游的封锁区域

O = 正在移动的对象

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

Answer 1

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

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

要有效地实施它，请查看：Change FloodFill-Algorithm to get Voronoi Territory for two data points? - 当我说标记时，你用你来自 + 1 的位置上的数字标记它。

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

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

您将 S 放入您的队列，然后 "expand" 它：

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

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

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

How to find the shortest path in 2D Array with multiple endpoints?

arrays

algorithm

shortest-path