用 Python 實作 Floyd-Warshall 演算法：從最短路徑到尋找最便宜機票

Floyd-Warshall 演算法，又稱佛洛伊德演算法，主要用於找出圖(graph)中所有頂點之間的最短路徑，它也能用來偵測圖中是否存在閉環(cycle)。

本文將使用 Python 學習 Floyd-Warshall 演算法，並且以找出城市與城市之間最便宜機票組合作為應用範例，讓讀者對 Floyd-Warshall 演算法有深入的了解。

本文環境 #

• Python 3

圖 / Graph #

在理解 Floyd-Warshall 演算法之前，須先了解何謂 graph。

Graph 是 1 種數學結構，用來表示頂點跟頂點之間的關係。

圖的基本元素分為：

• 頂點(Vertex)
• 邊(Edge)

例如下圖中的 A, B, C 是頂點，而連接 A, B, C 的 3 個箭頭則是代表 A, B, C 之間關係的邊，也就是 A 可以到達 B, C，而 B 只能到達 C，C 無法到達 A, B：

由於上圖的邊具有方向性，這種具有方向性的圖被稱為有向圖(Directed Graph)。而沒有方向性的圖則稱為無向圖(Undirected Graph)，這種圖的頂點之間的關係是雙向的，例如朋友關係通常可以用無向圖進行表示。

此外，上圖的邊也具有權重/成本的概念，可以表示頂點到頂點之間的距離、成本或其他度量，這種邊具有權重的圖則稱為加權圖(Weighted Graph)。

所以上圖其實是 1 個有向加權圖。

而這個圖可以用以下表格進行表示：

舉第 1 列為例，代表 A 到 A 點距離為 0， A 到 B 點距離為 1，A 到 C 點距離為 5。

舉第 2 列為例，由於 B 與 A 沒有連接，所以 B 到 A 點距離以無限 ∞ 進行表示， B 到 B 點距離為 0，B 到 C 點距離為 3。

以此類推。

程式如何表達 graph？ #

在程式的世界中，表達 graph 最簡單的方法就是使用 2 維矩陣，前述 A, B, C 的關係用 Python 的 List 進行表達的話：

from decimal import Decimal

inf = Decimal('inf')

graph = [
    [0, 1, 5],
    [inf, 0, 3],
    [inf, inf, inf],
]

上述 2 維矩陣也是接下來 Floyd-Warshall 演算法會使用到的資料結構，這種 2 維矩陣表達方式也稱為 Adjacency Matrix。

Floyd-Warshall 演算法簡介 #

Floyd-Warshall 演算法，又稱佛洛伊德演算法，主要用於找出圖(graph)中所有頂點之間的最短路徑，它也能用來偵測圖中是否存在閉環(cycle)。

Floyd-Warshall 演算法可以處理有向圖或負權的最短路徑問題，負權代表邊的權重可以為負值，但它不能處理存在負權閉環的情況，使用上必須注意。

以下是 Floyd-Warshall 演算法的虛擬碼。

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

for each vertex v
   dist[v][v] ← 0

for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)

for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] ← dist[i][k] + dist[k][j]
         end if

簡單解釋一下，前面 2 個 for 迴圈是建立前文所提到的 2 維矩陣(Adjacency Matrix)，如果點跟點之間不是直接連接，就設定距離為無限，第 3 個巢狀 for 迴圈則是計算每個點跟點的最短距離。

由於最後 1 個 for 迴圈是 1 個 3 層式的巢狀迴圈，人腦感到難以理解是正常的，但它的重點其實是最內層的 if 判斷式：

if dist[i][j] > dist[i][k] + dist[k][j]
   dist[i][j] ← dist[i][k] + dist[k][j]

把上述判斷式以一個範例圖進行表示的話：

它核心意思是——假如 i 點到 j 點的距離大於 i 到中間點 k 再從中間點 k 到 j 點的距離的話，就更新 i 到 j 點的最短距離。所以上圖的 i 的到 j 點的最短距離是 4。

Floyd-Warshall 演算法就是藉由把每個頂點當作中間點 k，算出每個點到點的最短路徑，也由於每個點到點都確保是最短路徑，所以最後 i 到 j 點之間經過不管幾個點都會是最短路徑。

從它的演算法也可以看出它的時間複雜度為 O(n^3)，空間複雜度為 O(n^2)， n 為頂點數。

Floyd-Warshall 演算法實際應用 — 找到點對點機票最低價 #

Floyd-Warshall 演算法的實際應用除了最短路徑之外，其實也可以用來找出怎麼轉機可以買到最低價的機票（當然本文沒有考慮轉機時間的問題）。

舉以下 5 個機場之間的機票價格（機票價格為邊的權重）為例：

以表格表示的話，如下：

如果我們想找出點跟點之間最便宜的票價，就可以使用 Floyd-Warshall 演算法：

import pprint
from decimal import Decimal

inf = Decimal('inf')

cities = ['TPE', 'HKG', 'TYO', 'AUS', 'SIN']
graph = [
    [0, 50, 30, 300, inf],
    [50, 0, inf, 220, inf],
    [30, inf, 0, inf, 60],
    [inf, 220, inf, 0, inf],
    [inf, inf, 60, 150, 0],
]

for k in range(len(cities)):
    for i in range(len(graph)):
        for j in range(len(graph[i])):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

pprint.pprint(graph)

上述 Python 程式碼執行結果如下：

[[0, 50, 30, 240, 90],
 [50, 0, 80, 220, 140],
 [30, 80, 0, 210, 60],
 [270, 220, 300, 0, 360],
 [90, 140, 60, 150, 0]]

我們再以表格表示：

從上述表格可以看到要從 TPE 到 AUS 最低價為 240（TPE -> TYO -> SIN -> AUS），比起從 TPE 直飛 AUS 省了 60。

如果有相似的問題也可以用 Floyd-Warshall 演算法解決！

總結 #

透過 Floyd-Warshall 演算法，我們不僅能輕鬆找出圖中所有頂點間的最短路徑，也能應用於實際問題，如城市間機票的最佳組合。

以上！

Enjoy!

References #

Floyd-Warshall演算法 - 維基百科，自由的百科全書

python algorithm