試題詳解

10 下列為有關使用 Dijkstra 演算法於圖形（Graph）結構 G 中尋找最短路徑（Shortest path）之敘述： ①Dijkstra 演算法僅適用於對邊線（Edge）具權值（Weight）之有向連接圖形（Directed connected graph） 結構 G 尋找最短路徑 ② 使用 Dijkstra 演算法可尋找 G 中自任一頂點（Vertex）至所有其他頂 點（Vertex）之最短路徑（Shortest path） ③使用 Dijkstra 演算法可尋找 G 中除了頂點（Vertex）v_A 以外之所有頂點（Vertex）至 v_A 之最短路徑（Shortest path） ④使用 Dijkstra 演算法對圖形（Graph） 結構 G 尋找最短路徑時，必須使用接鄰串列（Adjacency list）儲存 G ⑤使用 Dijkstra 演算法對圖形 （Graph）結構 G 找出之最短路徑中，若存在環路（Cycle），則組成該環路之所有邊線中，至少有 一邊線其權值（Weight）為負值。請選出最適合之選項：
(A)②正確；④⑤錯誤
(B)①正確；③④錯誤
(C)④正確；②⑤錯誤
(D)⑤正確；①④錯誤