申論 2給定一個無向圖G(V, E)，每個頂點代表一個地點，每條邊e (eE)代表一條道路，邊的正整數權重( e)表示該道路的塞車程度，數值越大越壅塞。對於一條從起點s 到終點t ( s ,t V)的路徑P，其最大塞車程度C(P)定義為路徑上所有邊權重的最大值：C(P)max(e )e P本題透過修改Dijkstra 最短路徑演算法中陣列d 的定義與更新方式，求出從s 到t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法流程與Dijkstra 最短路徑演算法相同，差異僅在於d [v ](vV)的定義與更新規則，其中，新的d [ v ]表示目前已知從s 到v 的路徑中，最大邊權重的最小值。初始時令d [ s ]0，其他頂點v 的d [v](vs)。之後依照Dijkstra演算法，每一輪選出尚未被選定且d 值最小的頂點u，並將原本的更新方式d [ v]min(d [ v],d [u](u , v))改為d [ v]min(d [ v], max(d [u ],(u , v)))，其中(u , v)為邊(u ,v) (u ,vV)的權重。重複進行，直到終點t 被選定為止。㈠以下列無向圖為例，令起點s 為A，終點t 為F，依照修改後的演算法，逐步列出每次選定一個頂點後陣列d 的變化過程。陣列中的頂點順序請依字母順序排列。（15 分）㈡說明修改後演算法之正確性，是基於d [ v ]更新規則具有何種性質。（5 分）㈢假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找出d 值最小者，可使用以下兩種方法：方法一：每次以線性方式掃描所有尚未選定的頂點找出最小d 值。方法二：使用最小堆積（min-heap）維護目前d 值最小的頂點。分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）