Learn the vocabulary of finding shortest paths correctly even when some edge weights are negative.
0 / 5 completed
1 / 5
At standup, a dev mentions finding shortest paths from a single source by relaxing every edge in the graph repeatedly, once per remaining node, which still works correctly even when some edge weights are negative. What is this algorithm called?
Bellman–Ford algorithm is exactly this: the Bellman–Ford algorithm finds shortest paths from a single source by relaxing, meaning attempting to improve, every edge in the graph on each of several passes, repeating one fewer time than the number of nodes, which correctly finds shortest paths even when some edge weights are negative, and can also detect a negative-weight cycle. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This repeated-relax-every-edge approach is exactly why the Bellman–Ford algorithm handles negative edge weights that would break Dijkstra's algorithm's closest-first assumption.
2 / 5
During a design review, the team picks the Bellman–Ford algorithm for a graph that may contain negative edge weights, specifically because Dijkstra's algorithm's closest-first strategy assumes non-negative weights and can give wrong answers if that assumption is violated. Which capability does this provide?
Bellman–Ford algorithm here provides Correct shortest paths even with negative edge weights, plus negative-cycle detection, since relaxing every edge repeatedly across the whole graph, rather than greedily finalizing the closest unvisited node the way Dijkstra's algorithm does, still converges to correct shortest distances even when some edges carry negative weight, and an extra pass can even detect a negative-weight cycle. Dijkstra's algorithm's closest-first strategy assumes every edge weight is non-negative and can produce wrong answers the moment that assumption is violated. This negative-weight tolerance is exactly why the Bellman–Ford algorithm is chosen over Dijkstra's algorithm whenever negative edge weights are possible.
3 / 5
In a code review, a dev notices a shortest-path feature over a graph that can contain negative edge weights, such as one modeling currency-arbitrage costs, uses Dijkstra's algorithm's closest-first strategy, which assumes every edge weight is non-negative, instead of an algorithm designed to tolerate negative weights. What does this represent?
This is a missed Bellman–Ford opportunity, since relaxing every edge repeatedly across the whole graph, the way the Bellman–Ford algorithm does, would still converge to correct shortest distances even with negative edge weights, unlike Dijkstra's non-negative-weight assumption. A cache eviction policy is an unrelated concept about discarded cache entries. This wrong-assumption pattern is exactly the kind of correctness bug a reviewer flags once negative edge weights are confirmed possible in the graph.
4 / 5
An incident report shows a shortest-path feature over a graph modeling costs that can go negative, such as currency arbitrage, produced silently wrong distances, because it used Dijkstra's algorithm, which assumes every edge weight is non-negative, instead of an algorithm tolerant of negative weights. What practice would prevent this?
Switching to the Bellman–Ford algorithm's repeated-relax-every-edge approach removes the non-negative-weight assumption entirely. Continuing to use Dijkstra's algorithm on a graph with possible negative edge weights regardless of whether any edge weight in the graph is actually negative is exactly what caused the issue described in this incident. This negative-weight-tolerant approach is the standard fix once the graph is confirmed to allow negative edge weights.
5 / 5
During a PR review, a teammate asks why the team reaches for the Bellman–Ford algorithm instead of Dijkstra's algorithm, given that Dijkstra's algorithm is generally faster. What is the reasoning?
The Bellman–Ford algorithm tolerates negative edge weights and can even detect a negative-weight cycle, at the cost of relaxing every edge across multiple passes instead of using a priority queue, while Dijkstra's algorithm is considerably faster thanks to its closest-first, priority-queue-driven strategy but produces wrong answers the instant a negative edge weight appears. This is exactly why the Bellman–Ford algorithm is chosen whenever negative weights are possible, while Dijkstra's algorithm remains the faster default when every weight is guaranteed non-negative.