高考申論題
115年
[資訊處理] 資料結構
第 鿪 題
📖 題組：
給定一個無向圖G = (V, E)，每個頂點代表一個地點，每條邊e(e∈E)代表一條道路，邊的正整數權重ω(e)表示該道路的塞車程度，數值越大越壅塞。對於一條從起點 s 到終點t(s, t ∈ V) 的路徑 P，其最大塞車程度C(P)定義為路徑上所有邊權重的最大值： $C(P) = \max_{e \in P} \omega(e)$ 本題透過修改 Dijkstra 最短路徑演算法中陣列 d 的定義與更新方式，求出從 s 到 t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法流程與 Dijkstra 最短路徑演算法相同，差異僅在於d[v](v ∈ V)的定義與更新規則，其中，新的d[v]表示目前已知從 s 到 v 的路徑中，最大邊權重的最小值。初始時令d[s] = 0，其他頂點 v 的d[v] = ∞ (v ≠ s)。之後依照 Dijkstra 演算法，每一輪選出尚未被選定且 d 值最小的頂點 u，並將原本的更新方式$d[v] = \min(d[v], d[u] + \omega(u,v))$改為$d[v] = \min(d[v], \max(d[u], \omega(u,v)))$，其中ω(u,v)為邊(u,v)(u, v ∈ V)的權重。重複進行，直到終點 t 被選定為止。
給定一個無向圖G = (V, E)，每個頂點代表一個地點，每條邊e(e∈E)代表一條道路，邊的正整數權重ω(e)表示該道路的塞車程度，數值越大越壅塞。對於一條從起點 s 到終點t(s, t ∈ V) 的路徑 P，其最大塞車程度C(P)定義為路徑上所有邊權重的最大值： $C(P) = \max_{e \in P} \omega(e)$ 本題透過修改 Dijkstra 最短路徑演算法中陣列 d 的定義與更新方式，求出從 s 到 t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法流程與 Dijkstra 最短路徑演算法相同，差異僅在於d[v](v ∈ V)的定義與更新規則，其中，新的d[v]表示目前已知從 s 到 v 的路徑中，最大邊權重的最小值。初始時令d[s] = 0，其他頂點 v 的d[v] = ∞ (v ≠ s)。之後依照 Dijkstra 演算法，每一輪選出尚未被選定且 d 值最小的頂點 u，並將原本的更新方式$d[v] = \min(d[v], d[u] + \omega(u,v))$改為$d[v] = \min(d[v], \max(d[u], \omega(u,v)))$，其中ω(u,v)為邊(u,v)(u, v ∈ V)的權重。重複進行，直到終點 t 被選定為止。
說明修改後演算法之正確性，是基於d[v]更新規則具有何種性質。（5 分）
📝 此題為申論題
思路引導 VIP
說明為何將 + 改成 max 後 Dijkstra 仍成立。Dijkstra 之所以正確，根源於權重的非負性與最佳子結構（Optimal Substructure），即路徑的單調不減性質。在瓶頸路徑中，取 max 同樣保證了新路徑的值必定大於等於先前的 d[u]，不會因為延伸路徑而變小，滿足貪婪選擇（Greedy choice）的單調性條件。
🤖
AI 詳解
AI 專屬家教
【考點分析】 Dijkstra 演算法的貪婪選擇性質與最佳子結構（Optimal Substructure），以及瓶頸半環（Bottleneck Semiring）的應用。 【理論/法規依據】
▼ 還有更多解析內容