DSABellman-Ford Algorithm
The Bellman-Ford Algorithm
The Bellman-Ford algorithm is best suited to find the shortest paths in a directed graph, with one or more negative edge weights, from the source vertex to all other vertices.
It does so by repeatedly checking all the edges in the graph for shorter paths, as many times as there are vertices in the graph (minus 1).
The Bellman-Ford algorithm can also be used for graphs with positive edges (both directed and undirected), like we can with Dijkstra's algorithm, but Dijkstra's algorithm is preferred in such cases because it is faster.
Using the Bellman-Ford algorithm on a graph with negative cycles will not produce a result of shortest paths because in a negative cycle we can always go one more round and get a shorter path.
A negative cycle is a path we can follow in circles, where the sum of the edge weights is negative.
Luckily, the Bellman-Ford algorithm can be implemented to safely detect and report the presence of negative cycles.
How it works:
- Set initial distance to zero for the source vertex, and set initial distances to infinity for all other vertices.
- For each edge, check if a shorter distance can be calculated, and update the distance if the calculated distance is shorter.
- Check all edges (step 2) \(V-1\) times. This is as many times as there are vertices (\(V\)), minus one.
- Optional: Check for negative cycles. This will be explained in better detail later.
The animation of the Bellman-Ford algorithm above only shows us when checking of an edge leads to an updated distance, not all the other edge checks that do not lead to updated distances.
Manual Run Through
The Bellman-Ford algorithm is actually quite straight forward, because it checks all edges, using the adjacency matrix. Each check is to see if a shorter distance can be made by going from the vertex on one side of the edge, via the edge, to the vertex on the other side of the edge.
And this check of all edges is done \(V - 1\) times, with \(V\) being the number of vertices in the graph.
This is how the Bellman-Ford algorithm checks all the edges in the adjacency matrix in our graph 5-1=4 times:
Checked all edges0 times.
The first four edges that are checked in our graph are A->C, A->E, B->C, and C->A. These first four edge checks do not lead to any updates of the shortest distances because the starting vertex of all these edges has an infinite distance.
After the edges from vertices A, B, and C are checked, the edges from D are checked. Since the starting point (vertex D) has distance 0, the updated distances for A, B, and C are the edge weights going out from vertex D.
The next edges to be checked are the edges going out from vertex E, which leads to updated distances for vertices B and C.
The Bellman-Ford algorithm have now checked all edges 1 time. The algorithm will check all edges 3 more times before it is finished, because Bellman-Ford will check all edges as many times as there are vertices in the graph, minus 1.
The algorithm starts checking all edges a second time, starting with checking the edges going out from vertex A. Checking the edges A->C and A->E do not lead to updated distances.
The next edge to be checked is B->C, going out from vertex B. This leads to an updated distance from vertex D to C of 5-4=1.
Checking the next edge C->A, leads to an updated distance 1-3=-2 for vertex A.
The check of edge C->A in round 2 of the Bellman-Ford algorithm is actually the last check that leads to an updated distance for this specific graph. The algorithm will continue to check all edges 2 more times without updating any distances.
Checking all edges \(V-1\) times in the Bellman-Ford algorithm may seem like a lot, but it is done this many times to make sure that the shortest distances will always be found.
Implementation of The Bellman-Ford Algorithm
Implementing the Bellman-Ford algorithm is very similar tohow we implemented Dijkstra's algorithm.
We start by creating theGraph class, where the methods__init__,add_edge, andadd_vertex will be used to create the specific graph we want to run the Bellman-Ford algorithm on to find the shortest paths.
class Graph: def __init__(self, size): self.adj_matrix = [[0] * size for _ in range(size)] self.size = size self.vertex_data = [''] * size def add_edge(self, u, v, weight): if 0<= u< self.size and 0<= v< self.size: self.adj_matrix[u][v] = weight #self.adj_matrix[v][u] = weight # For undirected graph def add_vertex_data(self, vertex, data): if 0<= vertex< self.size: self.vertex_data[vertex] = dataThebellman_ford method is also placed inside theGraph class. It is this method that runs the Bellman-Ford algorithm.
def bellman_ford(self, start_vertex_data): start_vertex = self.vertex_data.index(start_vertex_data) distances = [float('inf')] * self.size distances[start_vertex] = 0 for i in range(self.size - 1): for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: distances[v] = distances[u] + self.adj_matrix[u][v] print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}") return distancesLine 18-19:At the beginning, all vertices are set to have an infinite long distance from the starting vertex, except for the starting vertex itself, where the distance is set to 0.
Line 21:All edges are checked \(V-1\) times.
Line 22-23:A double for-loop checks all the edges in the adjacency matrix. For every vertexu, check edges going to verticesv.
Line 24-26:If the edge exist, and if the calculated distance is shorter than the existing distance, update the distance to that vertexv.
The complete code, including the initialization of our specific graph and code for running the Bellman-Ford algorithm, looks like this:
Example
Python:
class Graph: def __init__(self, size): self.adj_matrix = [[0] * size for _ in range(size)] self.size = size self.vertex_data = [''] * size def add_edge(self, u, v, weight): if 0<= u< self.size and 0<= v< self.size: self.adj_matrix[u][v] = weight #self.adj_matrix[v][u] = weight # For undirected graph def add_vertex_data(self, vertex, data): if 0<= vertex< self.size: self.vertex_data[vertex] = data def bellman_ford(self, start_vertex_data): start_vertex = self.vertex_data.index(start_vertex_data) distances = [float('inf')] * self.size distances[start_vertex] = 0 for i in range(self.size - 1): for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: distances[v] = distances[u] + self.adj_matrix[u][v] print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}") return distancesg = Graph(5)g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')g.add_vertex_data(2, 'C')g.add_vertex_data(3, 'D')g.add_vertex_data(4, 'E')g.add_edge(3, 0, 4) # D -> A, weight 4g.add_edge(3, 2, 7) # D -> C, weight 7g.add_edge(3, 4, 3) # D -> E, weight 3g.add_edge(0, 2, 4) # A -> C, weight 4g.add_edge(2, 0, -3) # C -> A, weight -3g.add_edge(0, 4, 5) # A -> E, weight 5g.add_edge(4, 2, 3) # E -> C, weight 3g.add_edge(1, 2, -4) # B -> C, weight -4g.add_edge(4, 1, 2) # E -> B, weight 2# Running the Bellman-Ford algorithm from D to all verticesprint("\nThe Bellman-Ford Algorithm starting from vertex D:")distances = g.bellman_ford('D')for i, d in enumerate(distances): print(f"Distance from D to {g.vertex_data[i]}: {d}")Negative Edges in The Bellman-Ford Algorithm
To say that the Bellman-Ford algorithm finds the "shortest paths" is not intuitive, because how can we draw or imagine distances that are negative? So, to make it easier to understand we could instead say that it is the "cheapest paths" that are found with Bellman-Ford.
In practice, the Bellman-Ford algorithm could for example help us to find delivering routes where the edge weights represent the cost of fuel and other things, minus the money to be made by driving that edge between those two vertices.
With this interpretation in mind, the -3 weight on edge C->A could mean that the fuel cost is $5 driving from C to A, and that we get paid $8 for picking up packages in C and delivering them in A. So we end up earning $3 more than we spend. Therefore, a total of $2 can be made by driving the delivery route D->E->B->C->A in our graph above.
Negative Cycles in The Bellman-Ford Algorithm
If we can go in circles in a graph, and the sum of edges in that circle is negative, we have a negative cycle.
By changing the weight on edge C->A from -3 to -9, we get two negative cycles: A->C->A and A->E->C->A. And every time we check these edges with the Bellman-Ford algorithm, the distances we calculate and update just become lower and lower.
The problem with negative cycles is that a shortest path does not exist, because we can always go one more round to get a path that is shorter.
That is why it is useful to implement the Bellman-Ford algorithm with detection for negative cycles.
Detection of Negative Cycles in the Bellman-Ford Algorithm
After running the Bellman-Ford algorithm, checking all edges in a graph \(V-1\) times, all the shortest distances are found.
But, if the graph contains negative cycles, and we go one more round checking all edges, we will find at least one shorter distance in this last round, right?
So to detect negative cycles in the Bellman-Ford algorithm, after checking all edges \(V-1\) times, we just need to check all edges one more time, and if we find a shorter distance this last time, we can conclude that a negative cycle must exist.
Below is thebellman_ford method, with negative cycle detection included, running on the graph above with negative cycles due to the C->A edge weight of -9:
Example
Python:
def bellman_ford(self, start_vertex_data): start_vertex = self.vertex_data.index(start_vertex_data) distances = [float('inf')] * self.size distances[start_vertex] = 0 for i in range(self.size - 1): for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: distances[v] = distances[u] + self.adj_matrix[u][v] print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}") # Negative cycle detection for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: return (True, None) # Indicate a negative cycle was found return (False, distances) # Indicate no negative cycle and return distancesLine 30-33:All edges are checked one more time to see if there are negative cycles.
Line 34:ReturningTrue indicates that a negative cycle exists, andNone is returned instead of the shortest distances, because finding the shortest distances in a graph with negative cycles does not make sense (because a shorter distance can always be found by checking all edges one more time).
Line 36:ReturningFalse means that there is no negative cycles, and thedistances can be returned.
Returning The Paths from The Bellman-Ford Algorithm
We are currently finding the total weight of the the shortest paths, so that for example "Distance from D to A: -2" is a result from running the Bellman-Ford algorithm.
But by recording the predecessor of each vertex whenever an edge is relaxed, we can use that later in our code to print the result including the actual shortest paths. This means we can give more information in our result, with the actual path in addition to the path weight: "D->E->B->C->A, Distance: -2".
This last code example is the complete code for the Bellman-Ford algorithm, with everything we have discussed up until now: finding the weights of shortest paths, detecting negative cycles, and finding the actual shortest paths:
Example
Python:
class Graph: def __init__(self, size): self.adj_matrix = [[0] * size for _ in range(size)] self.size = size self.vertex_data = [''] * size def add_edge(self, u, v, weight): if 0<= u< self.size and 0<= v< self.size: self.adj_matrix[u][v] = weight #self.adj_matrix[v][u] = weight # For undirected graph def add_vertex_data(self, vertex, data): if 0<= vertex< self.size: self.vertex_data[vertex] = data def bellman_ford(self, start_vertex_data): start_vertex = self.vertex_data.index(start_vertex_data) distances = [float('inf')] * self.size predecessors = [None] * self.size distances[start_vertex] = 0 for i in range(self.size - 1): for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: distances[v] = distances[u] + self.adj_matrix[u][v] predecessors[v] = u print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}") # Negative cycle detection for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][v]< distances[v]: return (True, None, None) # Indicate a negative cycle was found return (False, distances, predecessors) # Indicate no negative cycle and return distances def get_path(self, predecessors, start_vertex, end_vertex): path = [] current = self.vertex_data.index(end_vertex) while current is not None: path.insert(0, self.vertex_data[current]) current = predecessors[current] if current == self.vertex_data.index(start_vertex): path.insert(0, start_vertex) break return '->'.join(path)g = Graph(5)g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')g.add_vertex_data(2, 'C')g.add_vertex_data(3, 'D')g.add_vertex_data(4, 'E')g.add_edge(3, 0, 4) # D -> A, weight 4g.add_edge(3, 2, 7) # D -> C, weight 7g.add_edge(3, 4, 3) # D -> E, weight 3g.add_edge(0, 2, 4) # A -> C, weight 4g.add_edge(2, 0, -3) # C -> A, weight -3g.add_edge(0, 4, 5) # A -> E, weight 5g.add_edge(4, 2, 3) # E -> C, weight 3g.add_edge(1, 2, -4) # B -> C, weight -4g.add_edge(4, 1, 2) # E -> B, weight 2# Running the Bellman-Ford algorithm from D to all verticesprint("\nThe Bellman-Ford Algorithm starting from vertex D:")negative_cycle, distances, predecessors = g.bellman_ford('D')if not negative_cycle: for i, d in enumerate(distances): if d != float('inf'): path = g.get_path(predecessors, 'D', g.vertex_data[i]) print(f"{path}, Distance: {d}") else: print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")else: print("Negative weight cycle detected. Cannot compute shortest paths.")Line 19:Thepredecessors array holds each vertex' predecessor vertex in the shortest path.
Line 28:Thepredecessors array gets updated with the new predecessor vertex every time an edge is relaxed.
Line 40-49:Theget_path method uses thepredecessors array to generate the shortest path string for each vertex.
Time Complexity for The Bellman-Ford Algorithm
The time complexity for the Bellman-Ford algorithm mostly depends on the nested loops.
The outer for-loopruns \(V-1\) times, or \(V\) times in case we also have negative cycle detection. For graphs with many vertices, checking all edges one less time than there are vertices makes little difference, so we can say that the outer loop contributes with \(O(V)\) to the time complexity.
The two inner for-loopschecks all edges in the graph. If we assume a worst case scenario in terms of time complexity, then we have a very dense graph where every vertex has an edge to every other vertex, so for all vertex \(V\) the edge to all other vertices \(V\) must be checked, which contributes with \(O(V^2)\) to the time complexity.
So in total, we get the time complexity for the Bellman-Ford algorithm:
\[ O(V^3) \]
However, in practical situations and especially for sparse graphs, meaning each vertex only has edges to a small portion of the other vertices, time complexity of the two inner for-loops checking all edges can be approximated from \(O(V^2)\) to \(O(E)\), and we get the total time complexity for Bellman-Ford:
\[ O(V \cdot E) \]
The time complexity for the Bellman-Ford algorithm is slower than for Dijkstra's algorithm, but Bellman-Ford can find the shortest paths in graphs with negative edges and it can detect negative cycles, which Dijkstra's algorithm cannot do.
