Which of the following is a polynomial-time algorithm for finding the shortest path in a graph with non-negative edge weights?
Options
-
A.
Dijkstra Algorithm
-
B.
Brute Force Algorithm
-
C.
Exhaustive Search
-
D.
More than one of the above
-
E.
None of the above
Correct Answer (Detailed Explanation is Below)
A.
Dijkstra Algorithm
Detailed Explanation
- Dijkstra Algorithm: Finds shortest paths from a single source in graphs with non-negative edge weights.
- Time Complexity: With a binary heap, commonly O((V + E) log V).
- Important: Dijkstra's algorithm does not correctly handle negative edge weights in general.
OOps! You are currently offline.
