在 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 的演算法。