Implementing the Bellman-Ford Algorithm in Python
- Samul Black
- Aug 17, 2024
- 7 min read
Updated: Aug 7
The Bellman-Ford algorithm is a well-known algorithm for finding the shortest path from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative edge weights, making it more versatile, though slightly less efficient. In this blog, we’ll dive into the Bellman-Ford algorithm, understand how it works, and implement it step by step in Python.
What is the Bellman-Ford Algorithm?
The Bellman-Ford algorithm is a fundamental graph algorithm used to compute the shortest paths from a single source vertex to all other vertices in a weighted directed graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle negative edge weights, making it especially useful in situations involving costs, credits, or financial data where such weights occur naturally.
However, it has one limitation: Bellman-Ford cannot handle graphs that contain negative weight cycles—i.e., cycles where the total weight is negative. If such cycles exist, the algorithm will detect them and report their presence, as shortest paths cannot be properly defined in such cases (because you can keep reducing the path cost by cycling). Few of the use cases of this algorithm include:
Currency Arbitrage Detection: In financial applications, negative weight cycles can represent arbitrage opportunities.
Network Routing Protocols: Used in protocols like RIP (Routing Information Protocol) for routing decisions.
Graph Analysis Tools: To detect cycles that reduce path costs abnormally.
Project Planning: Finding dependencies and time estimations in graphs with negative delays.
The Bellman-Ford algorithm is a powerful solution when dealing with graphs that may include negative edge weights. While it's less efficient than Dijkstra’s algorithm for graphs with only non-negative weights, its ability to detect negative cycles makes it essential in many critical applications such as networking, finance, and path analysis. Few of its key features include:
Works on directed or undirected graphs (if undirected, treat as two directed edges).
Handles negative edge weights safely.
Detects negative weight cycles, unlike Dijkstra’s algorithm.
Time Complexity: O(V × E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) for storing distances.
How Does the Bellman-Ford Algorithm Work?
The Bellman-Ford algorithm works through a process known as edge relaxation. In each iteration, it checks all edges and updates the distance to the destination vertex if a shorter path is found via the edge. This operation is repeated |V| - 1 times, where |V| is the number of vertices in the graph. This is because, in the absence of negative cycles, the shortest possible path between any two vertices can contain at most |V| - 1 edges.
After all iterations, the algorithm performs one final pass through all edges to check for further relaxation. If a shorter path is still found, it indicates the existence of a negative weight cycle in the graph. Steps involved in this algorithm are:
Initialize distances
Set the distance to the source vertex as 0.
Set the distances to all other vertices as infinity.
Relax all edges repeatedly
Repeat this step exactly |V| - 1 times:
For each edge (u, v) with weight w,
If distance[u] + w < distance[v], then update distance[v] = distance[u] + w.
Detect negative weight cycles
Check all edges again one last time.
If a shorter path is still found, a negative weight cycle exists in the graph.
Bellman-Ford Algorithm Implementation in Python
Implementing the Bellman-Ford algorithm in Python allows you to find the shortest paths from a single source node to all other nodes in a graph, even when negative edge weights are present. This makes it an ideal choice for scenarios where traditional algorithms like Dijkstra fail due to negative costs. Below is a simple and readable Python implementation that demonstrates the core logic of the Bellman-Ford algorithm. Let’s implement the Bellman-Ford algorithm step by step.
def bellman_ford(graph, vertices, source):
# Step 1: Initialize distances from source to all vertices as infinite
distance = [float('inf')] * vertices
distance[source] = 0
# Step 2: Relax all edges |V| - 1 times
for _ in range(vertices - 1):
for u, v, weight in graph:
if distance[u] != float('inf') and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
# Step 3: Check for negative-weight cycles
for u, v, weight in graph:
if distance[u] != float('inf') and distance[u] + weight < distance[v]:
print("Graph contains a negative weight cycle")
return None
return distance
# Example usage:
edges = [
(0, 1, 6),
(0, 2, 7),
(1, 2, 8),
(1, 3, -4),
(1, 4, 5),
(2, 3, 9),
(2, 4, -3),
(3, 1, 7),
(4, 0, 2),
(4, 3, 7)
]
V = 5 # Number of vertices
source = 0
result = bellman_ford(edges, V, source)
if result:
for i, d in enumerate(result):
print(f"Shortest distance from node {source} to node {i} is {d}")
Output:
Shortest distance from node 0 to node 0 is 0
Shortest distance from node 0 to node 1 is 6
Shortest distance from node 0 to node 2 is 7
Shortest distance from node 0 to node 3 is 2
Shortest distance from node 0 to node 4 is 4In this Python implementation, the graph is represented as a list of edges where each edge is a tuple (u, v, weight)indicating a directed edge from vertex u to vertex v. We initialize the distances to all vertices as infinity, except for the source node which is set to 0. The main loop relaxes all edges V - 1 times, progressively updating the shortest known distances. After the relaxation phase, the algorithm performs an additional pass to detect any negative weight cycles. If such a cycle is found, the algorithm returns a warning and halts; otherwise, it prints the shortest distances from the source to all other nodes.
Related Algorithms to Bellman-Ford
The Bellman-Ford algorithm is closely related to a number of other graph algorithms that solve similar or complementary problems. These adjacent algorithms vary in how they handle negative weights, the type of shortest path problem they address, and their performance on different types of graphs. Below is an overview of the key algorithms that are related to Bellman-Ford, each serving specific use cases and offering different trade-offs.
Dijkstra’s Algorithm is one of the most well-known shortest path algorithms. It finds the shortest path from a single source to all other vertices in a graph, but it only works with non-negative edge weights. Dijkstra’s is typically faster than Bellman-Ford, especially when implemented with a priority queue, but it cannot handle negative weights. This makes Bellman-Ford more flexible in graphs where such edge weights exist.
Floyd-Warshall Algorithm is used to compute the shortest paths between all pairs of vertices in a weighted graph. It can handle negative edge weights, but it does not detect negative weight cycles. While Bellman-Ford focuses on single-source shortest paths, Floyd-Warshall solves the all-pairs shortest path problem. However, its time complexity is O(V³), making it more suitable for smaller graphs.
Johnson’s Algorithm combines the strengths of Bellman-Ford and Dijkstra’s algorithms to compute all-pairs shortest paths in sparse graphs with negative weights. It first uses Bellman-Ford to reweight the graph and remove all negative weights, then runs Dijkstra’s algorithm from each vertex. This makes Johnson’s algorithm more efficient than Floyd-Warshall in sparse graphs with negative edges but no negative cycles.
A-Star (A) Algorithm* is a heuristic-based pathfinding algorithm widely used in AI and game development. It extends Dijkstra’s algorithm by incorporating a heuristic that estimates the remaining cost to the goal, allowing it to focus on the most promising paths. While not directly related to Bellman-Ford in terms of weight handling, A* is often considered in applications requiring efficient and optimal pathfinding with domain-specific heuristics.
SPFA (Shortest Path Faster Algorithm) is an optimization of the Bellman-Ford algorithm. Instead of blindly relaxing all edges in each iteration, SPFA maintains a queue of vertices whose distances were updated, leading to better practical performance in many cases. While it shares Bellman-Ford’s ability to detect negative weight cycles, its worst-case time complexity remains the same.
Topological Sort with Relaxation is an approach used specifically for Directed Acyclic Graphs (DAGs). By performing a topological sort followed by edge relaxation, shortest paths can be found in linear time. This method is extremely efficient but limited to acyclic graphs. Since negative weight cycles cannot exist in DAGs, it safely handles negative weights without any special cycle detection.
Prim’s and Kruskal’s Algorithms are not used for shortest paths but are often mentioned alongside Bellman-Ford due to their role in graph theory. These algorithms are designed to find minimum spanning trees, which connect all vertices in a graph with the minimum total edge weight. Although they serve a different purpose, understanding them is helpful for comprehensive graph algorithm knowledge.
Summary Table
Conclusion
The Bellman-Ford algorithm is a powerful tool for finding shortest paths in graphs, particularly when dealing with graphs that may contain negative edge weights. Unlike Dijkstra’s algorithm, which fails in the presence of negative values, Bellman-Ford remains reliable and accurate, making it a preferred choice in many real-world applications such as financial modeling, network routing, and graph-based analytics where such edge weights are common.
While it is less efficient in terms of time complexity—especially for dense graphs—its ability to detect negative weight cycles provides a critical diagnostic feature that other algorithms lack. This makes it especially useful in situations where correctness and robustness are more important than speed.
By understanding and implementing the Bellman-Ford algorithm in Python, you can solve a variety of shortest path problems in weighted graphs with confidence. Whether you’re building a routing engine, performing cost analysis, or detecting anomalies in directed graphs, Bellman-Ford equips you with a versatile and essential algorithm that extends beyond basic pathfinding.
Mastering it not only deepens your knowledge of graph theory but also enhances your problem-solving toolkit for tackling more complex and realistic graph-based scenarios.
