# A deep dive into Bellman Ford’s algorithm

# What is Bellman Ford’s Algorithm?

It is an algorithm that helps us to compute the shortest path from a vertex to all other vertexes in a weighted graph. The following algorithm was first proposed by **Alfonso Shimbel** in **1955** but was named after **Richard Bellman** and **Lester Ford** **Jr**. in **1958** and **1956**. It is an upgraded version of Dijkstra’s Algorithm and a more flexible and adaptive algorithm as it is capable of handling the edges with negative weight.

# Can there be edges with negative weights in real life?

The answer is yes, there are many possibilities where you can find edges having negative weights in real life. For example, consider there are two chemicals, A and B. There are different ways to reach from chemical A to chemical B, involving sub-reactions like absorption and heat dissipation. So now, to find the reactions where minimum energy is required, then we will need to be able to factor in the heat absorption as negative weights and heat dissipation as positive weights.

# What are the limitations/disadvantages of Dijkstra’s algorithm?

When we use the algorithm for calculating the shortest path the assumption we make is that all the edges have positive weight, but from the above example we did come to know that in many cases there are negative weights too. Therefore, If we apply this algorithm where we have negative weights, the algorithm would fail to calculate the shortest paths correctly. The reason is that Path(source, destination) might be negative which will make it possible to reach the source from the destination at a lower cost.

# How Bellman Ford’s algorithm works?

Bellman Ford’s algorithm operates by calculating the path length from the starting vertex to all other vertices. It then relaxes those estimates iteratively by identifying new routes that are shorter than the previously overestimated paths. This is the base idea of doing it. For getting a clear image of it let’s understand it with an example.

Step 1: Start with the weighted graph.

Step 2: Choose a starting vertex and assign infinity path values to all other vertices.

Step 3: Visit each edge and relax the path distances if they are inaccurate.

Step 4: We need to do this V times because in the worst case, a vertex's path length might need to be readjusted V times.

Step 5: Notice how the vertex at the top right corner had its path length adjusted.

Step 6: After all the vertices have their path lengths, we check if a negative cycle is present.

# Algorithm and Pseudocode

In the previous section, we saw how the algorithm works with the help of an example. Now we will be focusing on the real criteria and conditions which are used by the algorithm to solve the problem.

The following steps are:

- The distances from the source to all vertices are set to infinity in this process, while the distance to the source itself is set to 0. An array distance[] is created of size | V | with all the values as infinity except the source vertex.
- The shortest distances are calculated in this step. Follow the steps below |V|-1 times, where |V| is the number of vertices in the graph. Do the following for each u-v edge.
**If distance[v] > distance[u] + edge uv weight, then distance[v] should be updated to distance[v] = distance[u] + weight if edge uv.** - This phase determines if the graph has a negative weight cycle. For each u-v edge, do the following, “Graph contains negative weight cycle”
**if distance[v] > distance[u] + edge weight uv.**

Step 2 ensures the shortest lengths if the graph does not have a negative weight cycle, which is the principle behind step 3. There is a negative weight loop if we iterate over all edges one more time to get a shorter path for every vertex.

The pseudo-code for the algorithm is:

`function bellmanFord(G, S)`

for each vertex V in G

distance[V] <- infinite

previous[V] <- NULL

distance[S] <- 0

for the number of vertex |v|-1

for each edge (U,V) in G

tempDistance <- distance[U] + edge_weight(U, V)

if tempDistance < distance[V]

distance[V] <- tempDistance

previous[V] <- U

for each edge (U,V) in G

If distance[U] + edge_weight(U, V) < distance[V}

Error: Negative Cycle Exists

return distance[], previous[]

# Implementation

The Bellman Ford’s algorithm implementation in c++ and python.

**C++ :**

#include <bits/stdc++.h>structEdge {intsrc, dest, weight;

};structGraph {

intV, E;

structEdge* edge;

};structGraph* createGraph(intV,intE)

{structGraph* graph =newGraph;

graph->V = V;

graph->E = E;

graph->edge =newEdge[E];

returngraph;

}voidprintArr(intdist[],intn){printf("Vertex Distance from Source\n");for(inti = 0; i < n; ++i)printf("%d \t\t %d\n", i, dist[i]);}voidBellmanFord(structGraph* graph,intsrc)

{

intV = graph->V;

intE = graph->E;

intdist[V];for(inti = 0; i < V; i++)

dist[i] = INT_MAX;

dist[src] = 0;for(inti = 1; i <= V - 1; i++) {

for(intj = 0; j < E; j++) {

intu = graph->edge[j].src;

intv = graph->edge[j].dest;

intweight = graph->edge[j].weight;

if(dist[u] != INT_MAX && dist[u] + weight < dist[v])

dist[v] = dist[u] + weight;

}

}for(inti = 0; i < E; i++) {

intu = graph->edge[i].src;

intv = graph->edge[i].dest;

intweight = graph->edge[i].weight;

if(dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

printf("Graph contains negative weight cycle");

return; // If negative cycle is detected, simply return

}

} printArr(dist, V);

return;

}main()

int

{

intV = 5; // Number of vertices in graph

intE = 8; // Number of edges in graph

structGraph* graph = createGraph(V, E);

graph->edge[0].src = 0;

graph->edge[0].dest = 1;

graph->edge[0].weight = -1; graph->edge[1].src = 0;

graph->edge[1].dest = 2;

graph->edge[1].weight = 4; graph->edge[2].src = 1;

graph->edge[2].dest = 2;

graph->edge[2].weight = 3; graph->edge[3].src = 1;

graph->edge[3].dest = 3;

graph->edge[3].weight = 2; graph->edge[4].src = 1;

graph->edge[4].dest = 4;

graph->edge[4].weight = 2; graph->edge[5].src = 3;

graph->edge[5].dest = 2;

graph->edge[5].weight = 5; graph->edge[6].src = 3;

graph->edge[6].dest = 1;

graph->edge[6].weight = 1; graph->edge[7].src = 4;

graph->edge[7].dest = 3;

graph->edge[7].weight = -3; BellmanFord(graph, 0);

return0;

}

**Python :**

classGraph:

def__init__(self, vertices):

self.V=vertices

self.graph=[]defaddEdge(self, u, v, w):

self.graph.append([u, v, w])defprintArr(self, dist):

print("Vertex Distance from Source")

foriinrange(self.V):

print("{0}\t\t{1}".format(i, dist[i]))defBellmanFord(self, src):

dist=[float("Inf")]*self.V

dist[src]=0for_inrange(self.V-1):

foru, v, winself.graph:

ifdist[u] !=float("Inf")anddist[u]+w < dist[v]:

dist[v]=dist[u]+wforu, v, winself.graph:

ifdist[u] !=float("Inf")anddist[u]+w < dist[v]:

print("Graph contains negative weight cycle")

returnself.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)g.BellmanFord(0)

# Time and space complexity analysis:

Though Bellman Ford algorithm is slower than Dijkstra’s Algorithm as it covers the negative weights which is one of the major drawback of Dijkstra’s algorithm, we prefer Bellman Ford’s algorithm more.

**Time Complexity:**

The total time of the Bellman-Ford algorithm is the sum of **initialization time, for loop time, and Relax function time.**

- For the
**best case**, the time complexity is**O(E)**. - For the
**average case**, the time complexity is**O(VE)**. - For the
**worst case**, the time complexity is**O(VE)**.

where V and E are vertices and edges.

**Space Complexity:**

The space complexity for Bellman Ford’s algorithm is **O(V)**.

# Conclusion

In this article, we took a deep dive into Bellman Ford’s algorithm getting to know about the working and the idea behind the algorithm. We also covered the need of the algorithm and how it overcomes the existing algorithm and studied the importance and existence of negative weight edges.