在 2D 图中查找源的最短路径

大多数情况下，我们需要找出从单一来源到所有其他节点或 2D 图中特定节点的最短路径。比如说：我们想知道一个骑士到达棋盘中某个方格需要多少动作，或者我们有一个阵列，其中一些细胞被阻挡，我们必须找出从一个细胞到另一个细胞的最短路径。我们只能水平和垂直移动。甚至对角线移动也是可能的。对于这些情况，我们可以转换节点中的方块或单元格，并使用 BFS 轻松解决这些问题。现在我们的访问，父级和级别将是 2D 数组。对于每个节点，我们将考虑所有可能的移动。要查找到特定节点的距离，我们还会检查是否已到达目的地。

还有一个叫做方向阵列的东西。这将简单地存储我们可以去的所有可能的方向组合。让我们说，对于水平和垂直移动，我们的方向数组将是：

+----+-----+-----+-----+-----+
| `dx` |  1  |  -1 |  0  |  0  |
+----+-----+-----+-----+-----+
| `dy` |  0  |   0 |  1  |  -1 |
+----+-----+-----+-----+-----+

这里 dx 表示在 x 轴上移动而 dy 表示在 y 轴上移动。这部分也是可选的。你也可以单独编写所有可能的组合。但使用方向数组处理它更容易。对角线移动或骑士移动可以有更多甚至不同的组合。

我们需要记住的另一部分是：

• 如果任何一个单元被阻塞，对于每个可能的移动，我们将检查该单元是否被阻塞。
• 我们还将检查我们是否超出了界限，即我们已越过数组边界。
• 将给出行数和列数。

我们的伪代码将是：

Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
    for j from 1 to column
        visited[i][j] := false
    end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
    top := Q.pop
    for i from 1 to m
        temp.x := top.x + dx[i]
        temp.y := top.y + dy[i]
        if temp is inside the row and column and top doesn't equal to blocksign
            visited[temp.x][temp.y] := true
            level[temp.x][temp.y] := level[top.x][top.y] + 1
            Q.push(temp)
        end if
    end for
end while
Return level

正如我们之前讨论的那样，BFS 仅适用于未加权的图形。对于加权图，我们需要 Dijkstra 的算法。对于负边缘周期，我们需要 Bellman-Ford 的算法。该算法再次是单源最短路径算法。如果我们需要找出从每个节点到所有其他节点的距离，我们需要 Floyd-Warshall 的算法。