The Bellman-Ford algorithm computes shortest paths from one source even when some edge weights are negative, provided no reachable negative-weight cycle makes the distances unbounded below.

It repeatedly relaxes every edge:

$$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr).$$

Any shortest simple path contains at most $|V|-1$ edges, so after $|V|-1$ full relaxation passes, every finite shortest-path distance has propagated through the graph.

A further pass provides a test for reachable negative cycles: if some distance can still decrease, such a cycle exists.

The running time is

$$O(|V||E|),$$

slower than Dijkstra's algorithm on nonnegative graphs but valid under more general weights. The contrast illustrates a common algorithmic trade-off: stronger assumptions can enable faster methods.