練習題

基礎題¶

1. 若某條路線的成本突然上升，你要修改圖中的哪個部分？

2. 為什麼最短路徑不一定代表「經過節點最少」？舉一個生活情境說明。

3. 有向圖和無向圖各適合描述哪一種日常情境？各舉一個例子。

4. 如果終點無法到達，程式應該回傳什麼訊息或例外？為什麼不應該默默回傳空路徑？

5. Dijkstra 在每一步都從優先佇列取出「成本最低的節點」，這樣做的用意是什麼？

實作題¶

1. 增加一個函式 all_shortest_distances，接受圖和起點，回傳從起點到所有可到達節點的最短成本字典。

2. 把節點改成部門名稱與簽核天數，模擬一條「從整理需求到送審」的最短簽核流程，並列印完整路徑。

3. 為 shortest_route 增加一個 max_cost 參數：若最短路徑成本超過這個上限，就回傳 None 而非拋錯。

4. 在原有圖結構上增加一個「反向查詢」功能：給定終點，找出所有可以到達它的起點。

反思題¶

• 用你自己的話說明：Dijkstra 和 BFS 的決策起點有什麼不同？

• 如果圖中出現負邊（成本為負數的邊），Dijkstra 還能正確運作嗎？你認為原因是什麼？

• 這一章的「路徑成本」是固定的數字。但真實工作裡，成本可能隨時間變動（例如尖峰時刻等候更久）。你會怎麼調整模型？