《演算法圖鑑》第四章：圖形搜尋
Published in
7 min readFeb 2, 2019
第四章主要在說明圖形搜尋演算法的便利處，可以應用在解決各式各樣的問題，像是找出計算機網路中通訊時間最短的路徑、鐵路路線中移動時間最短的路徑。依據搜尋的順序，可分為「廣度優先搜尋」和「深度優先搜尋」。
提到「圖形」( Graph )，多數人會聯想到報章雜誌常見的長條圖、圓餅圖，但是在計算機科學或離散數學所用的圖形如下，
圓點稱為「頂點」或「節點」，連接節點的線稱為「邊」。所以圖形的呈現有數個節點，並由邊倆倆相連接。
加權圖形 ( Weighted Graph )
而上圖中，在每個邊上都有數字，稱為邊的「加權」或「權重」，這類的圖形則稱為「加權圖形」( Weighted Graph )。
有向圖 ( Direct Graph )
要在圖形中表示某個邊只能單向，會在邊上端點加註方向，這類的圖形稱為「有向圖」( Direct Graph )。
廣度優先搜尋 ( Breadth-First Search )
- 廣度優先搜尋 ( Breadth-First Search )，假設自己在某個節點（ 也是起點 ），從起點經由邊搜尋指定的節點（ 目標節點 ），在搜尋時優先搜尋離起點較近的節點。又稱作「寬度優先搜尋」或「橫向優先搜尋」。
- 節點是用「先進先出」( FIFO ) 的方式管理，所以可以用「佇列」( Queue ) 的資料結構。
- 廣度優先搜尋具有從靠近起點的節點開始廣泛搜尋的特性，所以目標節點離起點越近。
深度優先搜尋 ( Depth-Frist Search )
- 深度優先搜尋 ( Depth-First Search )，從起點經由邊搜尋目標節點 ，在搜尋時優先搜尋縱向單一路徑，直到無法繼續前進再折返搜尋下一個路徑。
- 節點是用「後進先出」( LIFO ) 的方式管理，所以可以用「堆疊」( Stack ) 的資料結構。
- 深度優先搜尋具有深入單一路徑往下搜尋的特性，與廣度優先搜尋的搜尋順序大不相同。
廣度優先搜尋 V.S 深度優先搜尋
- 廣度優先搜尋優先選擇最早被加入的節點，因為先從最近的節點開始搜尋。
- 深度優先搜尋優先選擇最晚被加入的節點，所以搜尋時並不折返，而是一直深入新開發的路徑。
貝爾曼-福特演算法 ( Bellman-Ford Algorithm )
- 貝爾曼-福特演算法 ( Bellman-Ford Algorithm ) 是計算圖形最短路徑問題的演算法。
- 最短路徑問題是在加權圖形中，指定起點和目標節點後，求出從起點到目標節點之間權重總和最小的路徑。
- 求取最短路徑時，通常邊的權重用來表示時間、距離或費用，一般都不是負數，但是使用貝爾曼-福特演算法時，即便權重是負數仍然可以正確運作。
- 當加權圖形有迴圈且各邊權重總和為負數時，隨著不斷重複迴圈，路徑的權重也會隨之變小，可判定為「最短路徑不存在」。
- 科普一下演算法名稱由來，得名自開發者理查・貝爾曼 ( Richard Ernest Bellman ) 和萊斯特・福特 ( Lester Randolph Ford Jr. )。同時貝爾曼也是演算法「動態規劃」( Dynamic Programming ，DP ) 的開發者。
貝爾曼-福特演算法執行時間多長？
假設節點數為 n、邊數為 m，貝爾曼-福特演算法進行 n 次更新操作的循環後就停止，而每一次循環會檢視所有的邊一次，所以一循環的執行時間是 O(m) ，整體時間就是 O(nm)。
戴克斯特拉演算法 ( Dijkstra’s Algorithm )
- 戴克斯特拉演算法 ( Dijkstra’s Algorithm ) 是計算圖形最短路徑問題的演算法。
- 最短路徑問題是在加權圖形中，指定起點和目標節點後，求出從起點到目標節點之間權重總和最小的路徑。
- 求取最短路徑時，通常邊的權重用來表示時間、距離或費用，一般都不是負數，但是使用戴克斯特拉演算法且權重是負數時，有時候會無法正確求出最短路徑。因而戴克斯特拉演算法不適用於有負權重的圖形。
- 戴克斯特拉演算法著重於選擇節點，有效率的求出最短路徑，而非像貝爾曼-福特演算法會對所有邊進行權重計算和更新。
戴克斯特拉演算法的執行時間多長？
假設節點數為 n、邊數為 m，未仔細研究選好節點的執行時間是 O(n²)。
能對資料結構下功夫的話，執行時間能壓縮到 O(m + n log n)。
總結來說，如果沒有負權重的圖形，選擇執行時間較短的戴克斯特拉演算法較佳。邊有負權重時，則選用執行時間雖然較長但能正確求得最短路徑的貝爾曼-福特演算法。
