# 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] + вес ребра uv`then 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
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)

# 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:

## One Comment

1. Iqra Technology says:

Hi,

I hope you’re doing well. I’m from Iqra Technology, where we teach IT skills for free to folks who need a helping hand. Our IT courses are available online for free, and anyone can use training material to develop IT skills.

We’re excited about the chance to share our story on your website through a guest post. We think our work aligns with what you care about, and we’d love a link from your site to spread the word.

Thanks a bunch for considering this. Looking forward to hearing from you soon!

Thanks and Regards