試題詳解

40. Which of the following statements is NOT true?
(A) Dijkstra algorithm cannot correctly calculate the shortest paths if there exist negative edge weights in the graph.
(B) Bellman-Ford algorithm can detect negative cycles in a graph.
(C) Given an unweighted graph with a node v, employing Breadth-First Search (BFS) starting on v obtains the single-source shortest paths with source node v.
(D) Floyd-Warshall algorithm for finding all-pair shortest paths works for graph with negative edge weights (but with no negative cycles).
(E) The worst-case time and space complexities of the Floyd-Warshall algorithm are both θ(n³).