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

答案：登入後查看
統計： A(59), B(29), C(27), D(33), E(0) #1201231

詳解 (共 3 筆)

#4099267
①Dijkstra 演算法僅適用於對邊線...
(共 327 字，隱藏中）
前往觀看
8
0
#4860008

有高手可以解釋⑤嗎?

⑤使用 Dijkstra 演算法對圖形 （Graph）結構 G 找出之最短路徑中，若存在環路（Cycle），則組成該環路之所有邊線中，至少有 一邊線其權值（Weight）為負值。

存在環路與組成該環路之所有邊線中，至少有 一邊線其權值（Weight）為負值

這兩個沒有絕對關係也不是因果關係吧


我在網路上找到的資料

且絕大多數的戴克斯特拉演算法不能有效處理帶有負權邊的圖


Dijkstra的算法僅適用於具有非負邊的圖。這是因為它假設第一次將一個節點從隊列中彈出時，我們已經找到了到達該節點的最短路徑，並且即使您的負權重為負，也不一定是正確的。


2
0
#1511727
求解


1
1