地特四等申論題
114年
[統計] 資料處理概要
第 一 題
📖 題組：
一、給定以下有向加權圖（7 個節點 A~G，15 條有向邊） A→B: 2 A→C: 4 A→D: 5 B→C: 1 B→D: 6 B→E: 3 C→D: 5 C→E: 2 C→F: 3 D→F: 2 D→G: 5 E→F: 2 E→G: 4 F→E: 2 F→G: 1
一、給定以下有向加權圖（7 個節點 A~G，15 條有向邊） A→B: 2 A→C: 4 A→D: 5 B→C: 1 B→D: 6 B→E: 3 C→D: 5 C→E: 2 C→F: 3 D→F: 2 D→G: 5 E→F: 2 E→G: 4 F→E: 2 F→G: 1
📝 此題為申論題，共 3 小題
小題 (一)
執行 Dijkstra 演算法，逐步計算節點 A 到每個節點的最短距離與路徑。請以此例說明 Dijkstra 演算法的運作方式，寫出每一步目前的「A 到每個節點的最短距離」與「前接節點（predecessor）」。（15 分）
思路引導 VIP
看到 Dijkstra 演算法，首先要明確這是單源最短路徑演算法。解題時需準備兩個陣列或表格：一個記錄目前從起點 A 到各節點的最短距離（初始值 A 為 0，其餘為無窮大），另一個記錄前接節點（predecessor）。應按步驟展現：每次從尚未確定的節點中，挑選距離最小的節點加入確定集合，並更新其相鄰節點的距離（若透過該節點到達相鄰節點的距離比已知距離短，則進行鬆弛操作 relaxation）。需清楚表列每一步的變化，以展示對演算法流程的完全掌握。
小題 (二)
請寫出 A 到各節點的最短路徑與路徑長度。（5 分）
思路引導 VIP
本題只需將上一子題求得的「前接節點」回溯，反推從 A 到各節點的完整路徑即可。例如 G 的前接是 F，F 是 C，C 是 B，B 是 A，故路徑為 A->B->C->F->G。並列出最終計算的最短距離（路徑長度）。
小題 (三)
舉出兩個 Dijkstra 演算法實際上的應用。（10 分）
思路引導 VIP
思考 Dijkstra 作為「圖論中尋找單一源頭到其他點的最短距離」的特性，聯想現實生活中哪裡需要「找出最快/最短/成本最低的路徑」。常見的經典應用包含網路路由與地理導航。