高考申論題
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 被選定為止。
以下列無向圖為例，令起點 s 為 A，終點 t 為 F，依照修改後的演算法，逐步列出每次選定一個頂點後陣列 d 的變化過程。陣列中的頂點順序請依字母順序排列。（15 分）
📝 此題為申論題
思路引導 VIP
模擬 Modified Dijkstra 算法（也稱 Bottleneck Shortest Path 算法）。準備陣列 d [A..H]。初始 d[A]=0，其餘為 ∞。每輪挑出未選定的節點中 d 值最小者 (u)，並使用 d[v] = min(d[v], max(d[u], weight(u,v))) 更新其未選定鄰居，直至終點 F 被選中。
🤖
AI 詳解
AI 專屬家教
【考點分析】 圖形演算法中的 Dijkstra 變形（最大邊權重最小化，又稱瓶頸路徑 Bottleneck Path），考查逐步追蹤演算法狀態變化的能力。 【理論/法規依據】
▼ 還有更多解析內容