資料結構與演算法
要以戴克斯特拉演算法求出正確的最短路徑，關於圖的條件，下列何者正確？
- A圖中沒有環路（回到同一頂點的路徑）
- B邊沒有方向
- C所有邊的權重都在0以上
查看答案與解析
正確答案：C. 所有邊的權重都在0以上
戴克斯特拉演算法會確定未確定頂點中距離最小者。這是基於「經由其他頂點時距離只會增加、不會減少」的前提。若有負權重的邊，之後可能經由其他路徑使距離變短；例如在 S→A 為2、S→B 為3、B→A 為−2 的有向圖中，A 以2確定之後，才找到 S→B→A 的1。有負權重時，要使用貝爾曼-福特演算法等方法。即使有環路或邊有方向，只要權重都在0以上，就能使用戴克斯特拉演算法。
- A. 即使有環路，只要權重在0以上就能正確求出。道路網中有很多環路。
- B. 有方向的（有向）圖也能使用。
- C. 正確。有負權重時，已確定的距離之後可能變短。