本章目標理解節點、邊與權重如何描述真實流程與決策網路
了解 BFS 與 Dijkstra 的差異，並知道何時該用哪一種
用 Python 建立可重現的最短路徑求解流程
把通勤路線、簽核流程與任務依賴轉成可比較的路徑成本
情境與限制情境：你要在多條候選路線中選出成本最低的一條，例如通勤路徑、簽核流轉或跨部門協作流程
輸入：節點關係、邊權重、起點與終點
輸出：最短總成本與完整路徑
限制：圖可能不是完全連通，且必須能清楚指出找不到路徑的情況
可重現規則本章程式碼位置：
examples/ch05/本章核心模組：
examples/ch05/routing.py測試：
pytest -q tests/test_ch05_graphs_and_routing.py典型用途：通勤規劃、工單流轉、任務依賴分析
什麼是圖¶
在資料結構裡，「圖」不是長條圖或折線圖，而是一種由節點（node）和邊（edge）組成的結構。
用最直覺的方式來想：
節點是地點或狀態，例如辦公室、部門、流程步驟。
邊是兩個節點之間的連線，代表你可以從一個地方移動到另一個地方。
權重是這條邊的成本，例如通勤時間、審核天數、傳輸延遲。
舉一個辦公室簽核的例子。假設一份申請需要從「整理需求」出發，可以先走向「完成文件」，也可以走向「法務確認」，最後才到「送審」。每一步的等待天數不同，這就是圖的基本形狀。
整理需求 ──(2天)──> 完成文件 ──(3天)──> 送審
\ ↑
\──(5天)──> 法務確認 ──(1天)──────────/在程式裡，這張圖可以用一個字典來表示：
graph = {
"整理需求": {"完成文件": 2, "法務確認": 5},
"完成文件": {"送審": 3},
"法務確認": {"送審": 1},
"送審": {},
}每個鍵是一個節點，對應的字典裡記錄了鄰居節點與邊的成本。
有向圖與無向圖¶
圖依照邊的方向性，可以分成兩種：
| 類型 | 意思 | 生活情境 |
|---|---|---|
| 有向圖 | 邊有方向，A → B 不代表 B → A | 簽核流程、資料管線、網頁連結 |
| 無向圖 | 邊沒有方向，A — B 兩側都可走 | 道路地圖（雙向通行）、社交關係 |
本章使用的是有向圖：從「整理需求」可以走到「完成文件」，但流程不會逆轉。這對表達工作流程非常自然。
BFS 與 Dijkstra：找路的兩種方式¶
同樣是「從 A 到 B 怎麼走」，不同情境適合不同算法：
| 方法 | 適合情境 | 找到的是 |
|---|---|---|
| BFS（廣度優先搜尋） | 邊的成本全部相同（或不在乎成本） | 經過節點最少的路徑 |
| Dijkstra | 邊的成本不同（有權重） | 總成本最低的路徑 |
為什麼最短路徑不一定是「跳數最少」？
想像你要從台北到高雄。走國道可能只需「1 段路」，但路途遙遠；搭高鐵要「換乘 2 次」，但時間最短。如果你的目標是節省時間，那跳數少的那條路根本不是最好的選擇。
這就是 Dijkstra 比 BFS 更適合有成本場景的原因：它評估的是累積代價，而不是步數。
Dijkstra 的運作邏輯¶
Dijkstra 的核心想法是：
每次從「目前已知成本最低的未確認節點」開始擴展。
具體步驟如下：
把起點的成本設為 0，其他所有節點設為無限大。
用優先佇列（min-heap）維護「待探索的節點 + 目前已知最低成本」。
每次從優先佇列取出成本最低的節點，嘗試更新它的所有鄰居。
如果經過這個節點的路徑比先前記錄的更短，就更新並記下「從哪裡來」。
到達終點時停止，沿「從哪裡來」往回還原完整路徑。
用上面簽核流程的例子走一遍：
| 步驟 | 目前節點 | 已知最低成本 |
|---|---|---|
| 起始 | 整理需求 | 整理需求=0, 其他=∞ |
| 第 1 步 | 整理需求 | 完成文件=2, 法務確認=5 |
| 第 2 步 | 完成文件（成本 2 最低） | 送審=5（經完成文件） |
| 第 3 步 | 送審（成本 5） vs 法務確認（成本 5） | 法務確認→送審=6，不更新 |
| 結果 | 整理需求 → 完成文件 → 送審 | 總成本 = 5 天 |
實作範例¶
請參考 examples/ch05/routing.py。請在專案根目錄執行程式，以確保路徑正確。
from examples.ch05.routing import shortest_route
graph = {
"A": {"B": 4, "C": 2},
"B": {"D": 5},
"C": {"B": 1, "D": 8},
"D": {},
}
cost, path = shortest_route(graph, "A", "D")
print(cost) # 8
print(path) # ["A", "C", "B", "D"]這個例子中，A → B → D 看起來只走 2 步（跳數最少），但總成本是 9；而 A → C → B → D 走了 3 步，總成本卻只有 8。Dijkstra 正確地找出了成本更低的那條路。
示範流程包含：
用字典定義有向圖的鄰接關係與各邊權重
用優先佇列（
heapq）維護目前最低成本的待探索節點計算從起點到終點的最短總成本
沿
previous字典往回還原完整路徑處理無路可達與節點不存在的兩種例外情況
哪些問題可以用圖來想¶
圖不只是地圖問題專用。只要問題裡有「從 A 到 B，中間要經過哪些步驟」的結構，通常都可以用圖來描述：
| 日常情境 | 節點 | 邊的成本 |
|---|---|---|
| 通勤路線 | 車站、換乘點 | 行車時間、步行距離 |
| 簽核流程 | 部門、審核角色 | 審核天數、轉交等待時間 |
| 資料管線 | 資料轉換步驟 | 處理時間、儲存成本 |
| 任務依賴排序 | 任務節點 | 是否有前置依賴（下一章主題） |
當你開始用「節點 + 邊 + 成本」的方式看問題，很多原本覺得說不清楚的流程卡關，都會變得容易診斷。