高考申論題
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 被選定為止。
假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找出 d 值最小者，可使用以下兩種方法：
方法一：每次以線性方式掃描所有尚未選定的頂點找出最小 d 值。
方法二：使用最小堆積（min-heap）維護目前 d 值最小的頂點。
分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）
方法一：每次以線性方式掃描所有尚未選定的頂點找出最小 d 值。
方法二：使用最小堆積（min-heap）維護目前 d 值最小的頂點。
分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）
📝 此題為申論題
思路引導 VIP
分析兩種實作的時間複雜度。令頂點數為 V，邊數為 E。 方法一：每次找最小值需掃描 V 個點，共執行 V 次，花費 O(V^2)。更新相鄰邊的操作總共執行 E 次，每次 O(1)，花費 O(E)。總時間 O(V^2 + E) = O(V^2)。
🤖
AI 詳解
AI 專屬家教
【考點分析】 Dijkstra 演算法在不同資料結構（線性陣列 vs. 最小堆積）實作下的時間複雜度分析。 【理論/法規依據】
▼ 還有更多解析內容