問題詳情
五、給一個加權連通無向圖（weighted connected graph），所有邊線的加權值為正整數。使用下列的貪婪演算法（Greedy algorithm）尋找從出發的節點 Start 到目的地節點Goal 之最短路徑。 1 初始化集合 Path ={Start} 2 初始化集合 VisitedVertices ={Start} 3 如果 Start =Goal, 離開;否則,繼續第 4 步驟 4 找出具有最小加權值的邊線 edge（Start, v）其中 v 不在集合 VisitedVertices 內 5 將 {v} 加入集合 Path 6 將 {v} 加入集合 VisitedVertices 7 將 Start 設為 v 並執行第 3 步驟
【題組】⑴請問是否可以正確找到最短路徑？（10 分）
參考答案
答案：A
難度：非常簡單0.929293
統計：A(184),B(4),C(4),D(6),E(0)