Bellman-Ford Shortest Paths With Negative Weights
Shortest-path problems usually ask for the cheapest route from one vertex to another in a weighted graph. Road networks, computer links, project dependencies and currency exchanges can all be represented this way. When every edge has a non-negative cost, Dijkstra’s algorithm is often the natural choice. When some edges have negative weights, Bellman-Ford provides a dependable alternative.
This tutorial explains the algorithm, its relaxation process, complexity, Python implementation and negative-cycle detection. The method is useful when an edge may represent a gain, refund, discount or credit rather than a straightforward cost. For example, a logistics model might assign a negative adjustment to a route with a rebate, while a financial graph might use exchange-rate transformations that create negative edges.
Why Bellman-Ford Matters
A weighted directed graph contains vertices and edges. Each edge connects a source vertex to a destination vertex and carries a numerical weight. A path’s total cost is the sum of its edge weights. The shortest-path problem seeks the minimum total cost from a chosen source to every reachable vertex, or to one particular destination.
Bellman-Ford begins with a distance of zero for the source and infinity for every other vertex. It then examines every edge repeatedly, improving distances whenever it finds a cheaper route. This repeated improvement is called relaxation. Unlike a greedy method that permanently selects the nearest-looking vertex, Bellman-Ford remains able to revise earlier decisions.
Negative edges are perfectly valid as long as there is no reachable negative-weight cycle. A negative cycle is a loop whose total weight is below zero. Travelling around it repeatedly would reduce the path cost forever, so no finite shortest path exists for vertices affected by that cycle.
For broader algorithm references, the algorithms collection provides useful background on graph traversal, complexity and related problem-solving techniques. Bellman-Ford is a particularly good study in how a simple invariant can lead to a reliable, general-purpose algorithm.
How Relaxation Finds Better Routes
Suppose an edge goes from u to v with weight w. If the best known distance to u is distance[u], then reaching v through this edge costs:
distance[u] + w
If this value is smaller than the current distance[v], update both the distance and the predecessor of v. The predecessor lets us reconstruct the actual route after the computation finishes.
The key property is that any simple path contains at most V - 1 edges, where V is the number of vertices. After one full pass over all edges, every shortest path containing one edge can be discovered. After two passes, paths containing two edges can be discovered, and so on. Therefore, V - 1 passes are sufficient when no negative cycle is reachable from the source.
A final pass checks whether any edge can still be relaxed. If it can, a reachable negative cycle exists. This test is essential because returning apparently small distances without reporting the cycle would produce misleading results.
The basic pseudocode is:
distance[source] = 0
distance[all other vertices] = infinity
repeat V - 1 times:
changed = false
for each edge (u, v, weight):
if distance[u] is finite and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
changed = true
if changed is false:
stop early
for each edge (u, v, weight):
if distance[u] is finite and distance[u] + weight < distance[v]:
report a reachable negative cycle
Comparing Shortest-Path Methods
Bellman-Ford is not always the fastest option. Its value comes from handling negative weights and detecting reachable negative cycles with a straightforward procedure. Choosing an algorithm depends on the graph’s edge weights, structure and size.
| Algorithm | Negative edges | Negative-cycle detection | Time complexity | Typical use |
|---|---|---|---|---|
| Breadth-first search | No weighted costs | No | O(V + E) |
Unweighted graphs |
| Dijkstra | No | No | O((V + E) log V) with a heap |
Non-negative weights |
| Bellman-Ford | Yes | Yes | O(VE) |
General weighted directed graphs |
| Floyd-Warshall | Yes | Yes, for all pairs | O(V³) |
Small dense graphs |
| DAG shortest paths | Yes, if acyclic | A cycle violates the model | O(V + E) |
Directed acyclic graphs |
Here, V represents vertices and E represents edges. Bellman-Ford’s O(VE) running time can be expensive for large dense graphs. Its memory usage is usually O(V) for distances and predecessors, plus O(E) for the edge list.
Dijkstra can be much quicker, but it assumes that once a vertex is selected as the current minimum, its distance cannot later improve. A negative edge breaks that assumption. For example, a route with an initial cost of 4 might lead to an edge of -10, creating a total of -6 after a choice that looked more expensive at first.
In an Australian mapping application, a simplified Sydney road graph may use travel time as a non-negative weight, making Dijkstra suitable. A model that includes toll rebates, energy credits or commercial freight incentives could introduce negative adjustments, where Bellman-Ford is safer.
Implementing Bellman-Ford in Python
A convenient Python representation is a list of triples: (source, destination, weight). This makes it easy to scan every edge during each pass. The vertices can be strings, integers or any hashable values, although integer labels are common in programming challenges.
def bellman_ford(vertices, edges, source):
distance = {vertex: float("inf") for vertex in vertices}
predecessor = {vertex: None for vertex in vertices}
distance[source] = 0
for _ in range(len(vertices) - 1):
changed = False
for start, end, weight in edges:
if distance[start] == float("inf"):
continue
candidate = distance[start] + weight
if candidate < distance[end]:
distance[end] = candidate
predecessor[end] = start
changed = True
if not changed:
break
for start, end, weight in edges:
if distance[start] == float("inf"):
continue
if distance[start] + weight < distance[end]:
raise ValueError("Reachable negative cycle detected")
return distance, predecessor
The distance[start] == infinity check prevents an unreachable vertex from being used as though it had a real path. The early-stop condition improves average performance on graphs that settle quickly, although the worst-case complexity remains O(VE).
A route can be reconstructed by following predecessor links backwards:
def reconstruct_path(predecessor, source, target):
path = []
current = target
while current is not None:
path.append(current)
if current == source:
return path[::-1]
current = predecessor[current]
return []
For example, a graph involving warehouses in Melbourne, Adelaide and Perth could include a fuel credit as a negative edge adjustment. The output distance would describe the total modelled cost, while the predecessor map would show the selected sequence of locations. Real route planning needs extra constraints such as road closures and time windows, but the graph technique remains the same.
Understanding Negative Cycles
A negative cycle is different from an ordinary negative edge. Consider edges A → B with weight 2, B → C with weight -5, and C → A with weight 1. The cycle total is -2. Every extra trip around the cycle decreases the accumulated cost by another two units.
Bellman-Ford identifies this situation by performing one additional scan after the normal V - 1 passes. If a distance can still decrease, the improvement must involve a route with at least V edges. Such a route repeats a vertex, and the repeated portion contains a cycle. Since the distance improves, that cycle must have a negative total weight.
Only cycles reachable from the selected source matter for a single-source calculation. If a disconnected component contains a negative cycle, the algorithm should not report it when the source cannot reach that component. This is why the infinity guard appears in both the relaxation loop and the final cycle check.
Negative cycles can represent different things depending on the domain. In a financial graph, they may signal an arbitrage opportunity. In a scheduling model, they might reveal inconsistent constraints. In a cost graph, they may indicate a data-entry error, such as a discount that can be applied repeatedly without restriction.
For probability and simulation concepts that sometimes appear alongside graph-based modelling, the Markov chain methods review offers related mathematical context. Bellman-Ford itself is deterministic, but both topics benefit from carefully defining states, transitions and valid repeated operations.
Implementation And Review Checklists
A sound implementation depends on more than copying the relaxation loop. Check the graph representation, source assumptions and meaning of unreachable vertices. In a production service, inputs may come from several systems, so malformed edges and duplicate vertices should be handled deliberately.
Australian use cases can make these details concrete. A courier network serving Brisbane suburbs might treat delivery time as a weight, while a remote Western Australian mining network could attach fuel consumption and site credits to the same edges. Distances, costs and incentives should be documented so that a negative value has a clear interpretation rather than being an accidental sign error.
Before Running The Algorithm
- Set the source distance to zero and every other distance to infinity.
- Store each directed edge in the correct source-to-destination order.
- Keep predecessor values so that a route can be reconstructed.
- Confirm whether negative weights represent valid business rules.
- Decide how unreachable vertices should appear in the output.
When Results Look Wrong
- Check for integer overflow when implementing the algorithm in C.
- Verify that the infinity value is never added to an edge weight.
- Run the extra scan to detect reachable negative cycles.
- Test a graph with a negative edge but no negative cycle.
- Compare a small example by hand before benchmarking a large graph.
A practical test case should include a direct route, an indirect cheaper route, an unreachable vertex and, where relevant, a negative cycle. For an Australian audience, an example involving Sydney, Canberra and Melbourne can make directed edges intuitive, while a remote route can illustrate why an unusual cost or credit needs explicit documentation. The algorithm will then be easier to trust, debug and adapt to real software systems.