Bellman-Ford Algorithm

In anticipation of the start of the course “Algorithms for developers” prepared another translation of an interesting article.

---

Task: Given a graph and the initial vertex src in the graph, it is necessary to find the shortest paths from src to all vertices in this graph. The graph may contain edges with negative weights.

We have already discussed Dijkstra’s algorithm as a way to solve this problem. Dijkstra’s algorithm is a greedy algorithm, and its complexity is O (VLogV) (using the Fibonacci heap). However, Dijkstra does not work for graphs with negative edge weights, while Bellman-Ford is completely. The Bellman-Ford algorithm is even simpler than the Dijkstra algorithm, and is well suited for distributed systems. At the same time, its complexity is equal to O (VE), which is more than the indicator for Dijkstra’s algorithm.

Recommendation: Before moving on to viewing the solution, try to practice by yourself.

Algorithm

The following are detailed steps.

Input data: Graph and start vertex src.
Output: The shortest distance to all vertices from src. If a cycle of negative weight occurs, then the shortest distances are not calculated, a message is displayed indicating the presence of such a cycle.

1. At this step, the distances from the original vertex to all other vertices are initialized as infinite, and the distance to src itself is assumed to be 0. An array is created dist[] the size |V| with all values ​​equal to infinity, except for the element dist[src]where src Is the original vertex.
2. The second step calculates the shortest distances. The following steps must be completed. |V|-1 times where |V| – the number of vertices in this graph.
   • Perform the following for each edge. u-v:
     If dist[v] > dist[u] + вес ребра uvthen update dist[v]
dist [v] = dist [u] + вес ребра uv
3. In this step, it is reported whether a negative weight cycle is present in the graph. For each rib u-v You must do the following:
   • If dist[v] > dist[u] + вес ребра uv, then in the graph there is a cycle of negative weight.

The idea of ​​step 3 is that step 2 guarantees the shortest distance if the graph does not contain a cycle of negative weight. If we go over all the edges again and get a shorter path for any of the vertices, this will be a signal of the presence of a negative weight cycle.

How it works? As in other dynamic programming tasks, the algorithm calculates the shortest paths from the bottom up. First, it calculates the shortest distances, that is, paths with a length of no more than one edge. Then it calculates the shortest paths with a length of not more than two edges and so on. After i-th iteration of the outer loop, shortest paths with a length of not more than i ribs. In any simple way, there can be a maximum | V | -1 edges, so the outer loop is executed exactly | V | -1 time. The idea is that if we calculated the shortest path with no more than i edges, then iterating over all edges guarantees the shortest path with no more than i + 1 ribs (the proof is pretty simple, you can refer to this lecture or video lecture from MIT)

Example

Let’s look at the algorithm in the following graph example. Images taken from here.
Let the initial vertex be 0. Take all distances as infinite, except for the distance to the src. The total number of vertices in the graph is 5, so all the edges need to go 4 times.

Let the ribs be worked out in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( E, D). We get the following distances when the passage along the ribs was completed for the first time. The first line shows the initial distances, the second line shows the distances when the edges (B, E), (D, B), (B, D) and (A, B) are processed. The third line shows the processing distance (A, C). The fourth line shows what happens when (D, C), (B, C) and (E, D) are processed.

The first iteration ensures that all the shortest paths are no longer than the path of 1 edge. We get the following distances when the second pass on all edges is completed (the last line shows the final values).

The second iteration ensures that all shortest paths have a length of at most 2 edges. The algorithm runs along all edges 2 more times. Distances are minimized after the second iteration, so the third and fourth iterations do not update the distance values.
Implementation:

# Python program for Bellman-Ford's single source 
# shortest path algorithm. 

from collections import defaultdict 

# Class to represent a graph 
class Graph: 

	def __init__(self, vertices): 
		self.V = vertices # No. of vertices 
		self.graph = [] # default dictionary to store graph 

	# function to add an edge to graph 
	def addEdge(self, u, v, w): 
		self.graph.append([u, v, w]) 
		
	# utility function used to print the solution 
	def printArr(self, dist): 
		print("Vertex Distance from Source") 
		for i in range(self.V): 
			print("% d tt % d" % (i, dist[i])) 
	
	# The main function that finds shortest distances from src to 
	# all other vertices using Bellman-Ford algorithm. The function 
	# also detects negative weight cycle 
	def BellmanFord(self, src): 

		# Step 1: Initialize distances from src to all other vertices 
		# as INFINITE 
		dist = [float("Inf")] * self.V 
		dist[src] = 0


		# Step 2: Relax all edges |V| - 1 times. A simple shortest 
		# path from src to any other vertex can have at-most |V| - 1 
		# edges 
		for i in range(self.V - 1): 
			# Update dist value and parent index of the adjacent vertices of 
			# the picked vertex. Consider only those vertices which are still in 
			# queue 
			for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						dist[v] = dist[u] + w 

		# Step 3: check for negative-weight cycles. The above step 
		# guarantees shortest distances if graph doesn't contain 
		# negative weight cycle. If we get a shorter path, then there 
		# is a cycle. 

		for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						print "Graph contains negative weight cycle"
						return
						
		# print all distance 
		self.printArr(dist) 

g = Graph(5) 
g.addEdge(0, 1, -1) 
g.addEdge(0, 2, 4) 
g.addEdge(1, 2, 3) 
g.addEdge(1, 3, 2) 
g.addEdge(1, 4, 2) 
g.addEdge(3, 2, 5) 
g.addEdge(3, 1, 1) 
g.addEdge(4, 3, -3) 

# Print the solution 
g.BellmanFord(0) 

# This code is contributed by Neelam Yadav 

Output Values:

Notes:

1. Negative weights are found in various graph applications. For example, instead of increasing the cost of a path, we can benefit by following a specific path.
2. The Bellman-Ford algorithm works better for distributed systems (better than Dijkstra's algorithm). Unlike Dijkstra, where we need to find the minimum value of all the vertices, in Bellman Ford, edges are considered one at a time.

Exercises:

1. The standard Bellman-Ford algorithm reports shortest paths only if it does not have cycles of negative weight. Modify it so that it reports the shortest paths even if there is such a cycle.
2. Can we use Dijkstra's algorithm to find the shortest paths in a graph with negative weights? There is such an idea: calculate the minimum weight value, add a positive value (equal to the absolute value of the minimum weight value) to all weights and run the Dijkstra algorithm for the modified graph. Will such an algorithm work?

Simple implementation of the Bellman-Ford algorithm

Sources:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf