( )21.Which of the following algorithms does not work for Graphs with negative weights?
(A) Bellman–Ford Algorithm
(B) Dijkstra’s Shortest Path Algorithm
(C) Floyd Warshall Algorithm
(D) None of the above.

好的，我來為您翻譯並回答這個關於圖演算法的問題。

21. 下列哪一種演算法不適用於帶有負權重的圖？

這個問題詢問在處理帶有負權重邊的圖時，哪一種最短路徑演算法會失效或不適用。

我們來分析每個選項：

• (A) Bellman–Ford Algorithm (貝爾曼-福特演算法)：

  • 分析： 貝爾曼-福特演算法是一種能夠計算帶有負權重邊的圖中單一源點到所有其他節點的最短路徑的演算法。它特別擅長處理負權重邊，甚至能夠偵測出圖中是否存在負權重環 (negative-weight cycles)。如果存在負權重環，貝爾曼-福特演算法可以報告無法找到最短路徑。
  • 適用性： 適用於帶有負權重邊的圖。

• (B) Dijkstra’s Shortest Path Algorithm (戴克斯特拉最短路徑演算法)：

  • 分析： 戴克斯特拉演算法是廣泛使用的單一源點最短路徑演算法。它的核心思想是每次從未訪問的節點中選擇距離最短的那個，並擴展其鄰居。然而，這個「貪婪」的策略基於邊權重非負的假設。如果圖中存在負權重邊，戴克斯特拉演算法可能會錯誤地判定某條路徑為最短路徑，因為它一旦確定了某個節點的最短路徑，就不會再回頭修改。負權重邊的存在可能會導致算法在處理時「繞遠路」反而找到更短的路徑，而這與戴克斯特拉演算法的設計原則衝突。
  • 適用性：不適用於帶有負權重邊的圖。

• (C) Floyd Warshall Algorithm (弗洛伊德-沃爾歇爾演算法)：

  • 分析： 弗洛伊德-沃爾歇爾演算法是一種能夠計算所有節點對之間的最短路徑的演算法（All-Pairs Shortest Path）。它使用動態規劃的思想，並且可以正確處理帶有負權重邊的圖，只要圖中不包含負權重環。如果存在負權重環，它也能夠偵測到。
  • 適用性： 適用於帶有負權重邊的圖（但不能有負權重環）。

• (D) None of the above (以上皆非)：

  • 分析： 由於戴克斯特拉演算法確實不適用於帶有負權重邊的圖，因此這個選項是錯誤的。

結論：

在處理帶有負權重邊的圖時，戴克斯特拉最短路徑演算法會失效。

The final answer is B​