Algorithms · Question 18 · Easy
Algorithms question 18
Which algorithm finds single-source shortest paths correctly even when some edge weights are negative, as long as there is no negative-weight cycle?
- Prim's algorithm
- Kruskal's algorithm
- Bellman-Ford algorithm
- Dijkstra's algorithm
Answer and explanation
Answer: C. Bellman-Ford algorithm
Explanation: Bellman-Ford relaxes every edge V - 1 times, so it handles negative edge weights and can also detect negative cycles. Dijkstra's greedy choice can fail with negative edges, and Prim and Kruskal build minimum spanning trees, not shortest paths.
Previous: Which of the following sorting algorithms is stable in its standard… · Next: What is the worst-case time complexity of merge sort on n elements?
Practise algorithms
Try a fresh set of algorithms questions with an explanation after every answer, free and without signing up: Algorithms practice. Or sit a full placement mock test.
More algorithms questions
- Using the Master theorem, what is the solution of T(n) = 3T(n/2) + n?
- What is the best-case time complexity of linear search on an array of n…
- Which of the following sorting algorithms is stable in its standard…
- What is the worst-case time complexity of merge sort on n elements?
- What is the time complexity of finding the largest element in an unsorted…
- Bubble sort is applied to the array [4, 1, 3, 2] in ascending order. What does…
- Two sorted lists with 6 and 9 elements are merged into one sorted list using…
- An undirected weighted graph has the edges A-B 4, A-C 1, B-C 2, B-D 5, C-D 8…
- What is the solution of the recurrence T(n) = T(n - 1) + n, with T(1) = 1?
- Coins of ₹2, ₹3 and ₹5 are available in unlimited supply. In how many…
More technical & programming practice
Object-Oriented Programming · DBMS · SQL · Operating Systems · Computer Networks · Software Engineering · Cloud & DevOps · GenAI Basics
LogicWiz Exams home · All practice topics · Placement mock tests · Daily 10 challenge