民國115年 高考三級 資訊處理 資料結構
第2題
給定一個無向圖G (V, E) ，每個頂點代表一個地點，每條邊( E) e e 代 表一條道路，邊的正整數權重( )e 表示該道路的塞車程度，數值越大越 壅塞。…
題目
給定一個無向圖G (V, E) ，每個頂點代表一個地點，每條邊( E) e e 代 表一條道路，邊的正整數權重( )e 表示該道路的塞車程度，數值越大越 壅塞。對於一條從起點s 到終點( , V) t s t 的路徑P，其最大塞車程度C(P) 定義為路徑上所有邊權重的最大值： C(P) max ( ) e P e 本題透過修改Dijkstra 最短路徑演算法中陣列d 的定義與更新方式，求出 從s 到t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法 流程與Dijkstra 最短路徑演算法相同，差異僅在於 ( ) [ ] V d v v 的定義與更新 規則，其中，新的[ ] d v 表示目前已知從s 到v 的路徑中，最大邊權重的最 小值。初始時令[ ] d s ，其他頂點v 的 ) [ ( ] d v v s 。之後依照Dijkstra 演算法，每一輪選出尚未被選定且d 值最小的頂點u，並將原本的更新方 式[ ] min [ ], ) ] ( [ ( , ) d v d v d u u v 改為[ ] min [ ], ma ) x [ ] , ) ( ( ( ) , d v d v d u u v ， 其中( , ) u v 為邊( ) ( ) , , V u v u v 的權重。重複進行，直到終點t 被選定為止。 以下列無向圖為例，令起點s 為A，終點t 為F，依照修改後的演算 法，逐步列出每次選定一個頂點後陣列d 的變化過程。陣列中的頂點 順序請依字母順序排列。（15 分） 說明修改後演算法之正確性，是基於[ ] d v 更新規則具有何種性質。（5 分） 假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找 出d 值最小者，可使用以下兩種方法： 方法一：每次以線性方式掃描所有尚未選定的頂點找出最小d 值。 方法二：使用最小堆積（min-heap）維護目前d 值最小的頂點。 分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）
參考解答（AI 生成，非官方）
- 一、題目資料缺漏之處理：本題圖形的邊集合及各邊權重未隨題文提供，僅知頂點A至F、起點A、終點F，因此無法唯一決定每輪選定的頂點與d值序列；題目資料缺漏，無法得出唯一數值。以下列出可直接套用的公式、表格格式與判定規則，補上原圖後即可逐輪填入。
- 二、初始化與更新公式：令d[A]=0，其餘d[v]=∞。每輪從尚未選定頂點中選d最小者u，對每個相鄰v執行d[v]=min(d[v], max(d[u], w(u,v)))。若t被選定即停止。表格可設欄位：輪次、選定u、d[A]、d[B]、d[C]、d[D]、d[E]、d[F]、本輪鬆弛的邊；d值依A至F字母順序排列。
- 三、逐步記錄要領：第一輪必選A，將A的鄰邊鬆弛；第二輪選當時d最小者，依此類推。每次只更新「經由u」可使瓶頸下降的鄰點；若max(d[u],w)不小於原d[v]則保留。沿路徑延伸時瓶頸值不減，且已選定頂點的d值依序單調不減，最後d[F]即為最大塞車程度的最小值。
- 四、正確性基礎：此演算法屬於瓶頸路徑（bottleneck path）的Dijkstra變形。其更新運算具有單調性與最優子結構（optimal substructure）：任何從s到v的路徑，其瓶頸值等於前一條到u的瓶頸值與邊(u,v)權重的較大者；延伸路徑只會使瓶頸值不減。因此每次選出最小d者時，不可能再經由其他未選點得到更小瓶頸，具備貪心選擇與切割性質（cut property）。
- 五、複雜度：方法一每輪線性掃描未選點，選點共O(V^2)，加上相鄰串列（adjacency list）鬆弛O(E)，總時間O(V^2+E)=O(V^2)。方法二以二元最小堆積（min-heap）維護，每次取出與插入O(log V)，每條邊最多觸發一次鬆弛，總O((V+E)log V)；若用減少鍵值（decrease-key）可達O(E+V log V)。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。