Question:medium

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

The Correct Option is C

Solution and Explanation

Idea: Ask what breaks Dijkstra but not Bellman-Ford.

Dijkstra locks in a vertex once picked and never revisits it, so a later negative edge cannot correct the distance. It therefore cannot cope with, or flag, negative cycles.

Bellman-Ford instead relaxes every edge repeatedly. After $|V| - 1$ rounds all true shortest distances are fixed if no negative cycle exists. Run one more round:
\[ \text{if } dist[v] > dist[u] + w(u,v) \text{ still improves, a negative cycle is present} \]

because in a graph with no negative cycle nothing can improve after $|V| - 1$ rounds. That extra check is the feature Dijkstra lacks.
\[\boxed{\text{Negative weight cycles}}\]
Was this answer helpful?
0