Question:
What can the Bellman-Ford algorithm detect that Dijkstra's algorithm cannot?
What can the Bellman-Ford algorithm detect that Dijkstra's algorithm cannot?
Show Hint
Dijkstra needs non-negative weights. Bellman-Ford does an extra relaxation pass to catch something Dijkstra cannot.
Updated On: Jul 2, 2026
- The shortest path in a weighted graph
- The longest path in a graph
- Negative weight cycles
- Cycles in a graph
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Dijkstra's algorithm assumes all edge weights are non-negative. It fails when negative edges are present, and it cannot report negative cycles.
Step 2: Bellman-Ford handles negative edge weights. It relaxes all edges \( |V| - 1 \) times to settle shortest paths.
Step 3: After those passes it runs one extra pass. If any edge can still be relaxed, a shortest path keeps getting smaller, which means a negative weight cycle exists. Bellman-Ford reports this.
Step 4: Both can find shortest paths, so A is not the distinguishing feature. The unique ability is detecting negative weight cycles, option C.
Step 2: Bellman-Ford handles negative edge weights. It relaxes all edges \( |V| - 1 \) times to settle shortest paths.
Step 3: After those passes it runs one extra pass. If any edge can still be relaxed, a shortest path keeps getting smaller, which means a negative weight cycle exists. Bellman-Ford reports this.
Step 4: Both can find shortest paths, so A is not the distinguishing feature. The unique ability is detecting negative weight cycles, option C.
Was this answer helpful?
0
0
Top CPET Computer Science Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions
Top CPET Algorithms - Sorting Questions
Top CPET Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions