Bellman-Ford Algorithm

Spotting one

Two tells, and either is enough on its own.

A cost somewhere can be negative. A refund, a gain, a discount. Dijkstra breaks here and this does not.

Or the question caps how many steps you may take. At most k stops, within k moves. That cap maps straight onto how the method works.

The idea, plainly

Go over every connection and improve any route it can improve. Then do it again. And again.

After one round you know the best routes that use one step. After two rounds, two steps. Which is why a limit of k stops is natural here. You stop after k rounds.

Where to start

Shortest Path With Negative Weights first, with no extra twist on top.

Then Cheapest Flights Within K Stops, where the round count is the constraint. One warning, because it catches nearly everyone: inside a single round you have to improve routes using the values from the end of the previous round, not values you just updated in this one. Mix them and a route quietly takes more stops than allowed.

Detect a Negative Cycle adds one idea. After enough rounds nothing should improve. If something still improves on one extra round, there is a loop that keeps getting cheaper forever.

Currency Arbitrage Detection is the same check in a suit. Exchange rates multiply rather than add, and taking logarithms turns multiplying into adding, which turns a loop that multiplies to more than one into a loop with a negative total.

Common mistakes

Using freshly updated values inside the same round, as above.

Stopping one round early and missing a negative loop.

Reading a negative loop as there is no answer. It only means there is no answer for the points that can reach that loop.