6. 以下關於求最短路徑演算法的敘述何者不正確？
(A) Bellman-Ford演算法可處理圖中某一邊之權值為負的情形
(B) Dijkstra演算法適用對圖中無負權值邊的圖求多源最短路徑
(C) Bellman-Ford演算法是一種動態規劃(Dynamic Programming)
(D) Floyd-Warshall 演算法是一種動態規劃(Dynamic Programming)

答案：登入後查看
統計： A(19), B(40), C(17), D(12), E(0) #3131023

詳解 (共 3 筆)

#6062030
Dijkstra演算法用於尋找圖上兩個頂...
(共 82 字，隱藏中）
前往觀看
3
0
#6345606
Dijkstra 演算法適用於 單源最短路徑 (Single Source Shortest Path, SSSP)，而非「多源最短路徑」。此外，Dijkstra 只能處理 非負權重的圖，否則會產生錯誤的結果
ㅤㅤ
Dijkstra 演算法 屬於貪婪演算法
0
0
#6441921

下列關於最短路徑演算法的敘述：

  • (A) Bellman-Ford演算法可處理圖中某一邊之權值為負的情形

    • 正確。Bellman-Ford 演算法的一個主要優勢就是能夠處理帶有負權重邊的圖，並且能夠檢測出負權重迴圈（negative cycle）。

  • (B) Dijkstra演算法適用對圖中無負權值邊的圖求多源最短路徑

    • 不正確。Dijkstra 演算法確實要求圖中沒有負權值邊（即所有邊的權值都必須是非負數）。然而，Dijkstra 演算法是一個單源最短路徑演算法（Single-Source Shortest Path Algorithm），它用於找到從單一指定起點到圖中所有其他節點的最短路徑。它並非設計來一次性求解「多源最短路徑」（Multi-Source Shortest Path）問題，雖然可以重複執行 Dijkstra 演算法來解決多源或所有配對的最短路徑問題，但其本身的定義是單源演算法。

  • (C) Bellman-Ford演算法是一種動態規劃(Dynamic Programming)

    • 正確。Bellman-Ford 演算法透過迭代地放鬆（relax）圖中的所有邊，逐步找出從源點到所有其他節點的最短路徑，其原理符合動態規劃的思想。

  • (D) Floyd-Warshall 演算法是一種動態規劃(Dynamic Programming)

    • 正確。Floyd-Warshall 演算法是一個所有配對最短路徑演算法（All-Pairs Shortest Path Algorithm），它使用動態規劃的方法來計算圖中所有節點對之間的最短路徑。

因此，不正確的敘述是 (B)。

The final answer is B​

0
0