Algorithms / Shortest Paths Weight Signs
Least You Need to Know: Dijkstra, Bellman-Ford, and Edge-Weight Assumptions
Shortest-path algorithms are chosen by the structure of the edge weights. Dijkstra relies on nonnegative weights so finalized distances never need revision, while Bellman-Ford handles negative edges and can detect reachable negative cycles through repeated relaxation.
The least you need to know
- Dijkstra is correct when all edge weights are nonnegative.
- Bellman-Ford can handle negative edges and can report reachable negative cycles.
- Relaxation means improving a distance estimate using one edge.
- BFS is the right tool for unweighted or equal-weight shortest-path problems.
- The key algorithm choice is determined by the edge-weight model.
Key notation
relaxation
replace a distance estimate with a smaller one when an edge offers improvement
negative cycle
a cycle whose total weight is negative
finalized vertex
a vertex whose shortest-path distance is settled in Dijkstra
Tiny worked example
- If all weights are nonnegative, Dijkstra can safely finalize the nearest not-yet-final vertex.
- If negative edges exist, that monotonicity can fail.
- Bellman-Ford instead performs repeated relaxation rounds.
- A further improvement after `|V|-1` rounds reveals a reachable negative cycle.
Common mistakes
- Students often use Dijkstra on graphs with negative edges because the graph 'looks small.' The weight sign assumption still matters.
- Bellman-Ford handles negative edges, but negative cycles make shortest paths undefined when reachable.
- Unweighted shortest paths are often just BFS in disguise.
How to recognize this kind of problem
- The prompt mentions edge weights and asks for shortest paths from a source.
- The first checkpoint is whether any edge can have negative weight.
- Relaxation or negative-cycle detection language appears.