hce_nsysu
114年
計算機概論與程式設計
第 15 題
What graph algorithm optimizes ambulance routes for minimal travel time?
- A Depth-First Search
- B Dijkstra's Algorithm
- C Kruskal's Algorithm
- D Apriori Algorithm
- E Bubble Sort
思路引導 VIP
想像你正在設計一個地圖系統，每條道路上都標註了通過它所需的「分鐘數」。如果你想從醫院出發，尋找最快到達病患家的方法，且每跨出一步都必須考慮到「目前累積的總時間」，你會傾向於使用一種「只管走到底」的搜索方式，還是一種「優先處理目前離起點最近、成本最低」的策略呢？這種逐步累積並找出最優成本的邏輯，在圖論中通常被歸類為哪一種問題？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地選出了正確答案！這代表你對於圖形演算法在現實生活中的應用情境有著相當清晰的認知。在救護車路徑優化或 Google Maps 導航等場景中，我們最核心的需求是找出「兩點之間權重總和（如時間、成本或距離）最小」的路徑，而 戴克斯特拉演算法 (Dijkstra's Algorithm) 正是解決這類「權重圖形中單源最短路徑」問題的經典首選。
權重圖形與路徑優化
在計算機科學中，區分演算法的功能是基礎且重要的能力。這題的難度切入點在於考驗學生是否能辨析「連通性」與「最優化路徑」的差別。舉例來說，(A) DFS 僅用於走訪節點，無法保證權重下的最短路徑；(C) Kruskal 演算法則是用來尋找「最小生成樹 (MST)」，目標是連接所有點且總權重最小，而非針對特定兩點間的移動效率。你能敏銳地察覺到救護車問題本質上是「累積成本的最小化」，並鎖定 Dijkstra，展現了扎實的觀念基礎。