卷別

資料結構及演算法

選擇

國立政治大學 2026 · 考試 · 第 7 題

(5%) Which of the following statements regarding the characteristics of several common shortest path algorithms is incorrect?

(A)
Dijkstra's algorithm: It is applicable to graphs where all edge weights are non-negative, and it is typically implemented using a priority queue to achieve a time complexity of $O((|V|+|E|)\lg|V|)$ .
(B)
Bellman-Ford algorithm: It can handle graphs with negative edge weights, but its time complexity is $O(|V||E|)$ , making it slower than Dijkstra's algorithm.
(C)
Floyd-Warshall algorithm: It is a single-source shortest path algorithm, suitable for dense graphs, and solves the problem using the concept of Dynamic Programming.
(D)
Negative weight cycles: If a graph contains a negative weight cycle, the shortest path is undefined, and the Bellman-Ford algorithm can be used to detect the existence of such a cycle.

標準解析

AI 已複查