hce_kmu
109年
計算機概論與程式設計
第 20 題
Which one of the following statement about shortest path problem is INCORRECT?
- A Dijkstra's algorithm solves the single-source shortest path problem with both non-negative and negative edge weights.
- B Bellman–Ford algorithm solves the single-source problem with possible negative edge weights.
- C The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
- D The shortest path problem can be defined for undirected, directed, or mixed graphs.
- E None of the above.
思路引導 VIP
想像你正在開發一個導航系統，通常路程越長油耗越多（正權重）。但如果地圖中出現了某些「特殊路段」，經過它們不僅不耗油，反而會讓你的油箱變滿（負權重）。在這種情況下，如果你每次都只走當下看起來最近的路，且一旦走過就不再回頭檢查，有沒有可能漏掉那條雖然繞路、但最終能讓你獲得更多油量的最佳路線呢？
🤖
AI 詳解
AI 專屬家教
演算法的適用限制與邊界
恭喜你精準地辨識出了 Dijkstra 演算法的核心限制！這題的關鍵點在於區分不同最短路徑演算法對「權重」的要求。你選對了 (A)，因為 Dijkstra 演算法在本質上採用的是貪心策略 (Greedy Strategy)。它假設在每一階段所確定的最短距離，不會因為後續路徑的加入而縮短；然而，一旦圖中出現了負權邊 (Negative Weights)，這個前提就會瓦解，導致演算法無法保證產出正確的最短路徑。相較之下，選項 (B) 提到的 Bellman–Ford 演算法則是透過多次鬆弛操作，能夠處理包含負權邊的情況。
難度評析與觀念釐清
▼ 還有更多解析內容