What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Bellman Ford Algorithm (Python Code with Example)

  • Jun 09, 2021
  • 7 Minutes Read
 Bellman Ford Algorithm (Python Code with Example)

In this article, we will study the bellman ford algorithm along with its python code. Also, we will study the example and its corresponding output. Lastly, we will know the time complexity and application of bellman ford in the real world.

What is Bellman-Ford Algorithm?

Bellman-Ford algorithm is used to find the shortest path from the source vertex to every vertex in a weighted graph. Unlike Dijkstra's algorithm, the bellman ford algorithm can also find the shortest distance to every vertex in the weighted graph even with the negative edges. The only difference between the Dijkstra algorithm and the bellman ford algorithm is that Dijkstra's algorithm just visits the neighbour vertex in each iteration but the bellman ford algorithm visits each vertex through each edge in every iteration.

Apart from Bellman-Ford Algorithm and Dijkstra's Algorithm, Floyd Warshall Algorithm is also the shortest path algorithm. But Bellman-Ford algorithm is used to compute the shortest path from the single source vertex to all other vertices whereas Floyd-Warshall algorithms compute the shortest path from each node to every other node.

Bellman ford algorithm follows the dynamic programming approach by overestimating the length of the path from the starting vertex to all other vertices. And then it starts relaxing the estimates by discovering the new paths which are shorter than the previous ones. This process is followed by all the vertices for N-1 times for finding the optimized result. 

Algorithm 

Begin

   count := 1

   maxEdge := a * (a - 1) / 2     //a is number of vertices



   for all vertices n of the graph, do

      distance[n] := 

      pred[n] := ?

   done



   distance[source] := 0

   eCount := number of edges in the graph

   create edge list named edgeList



   while count < a, do

      for k := 0 to eCount, do

         if distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k) distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k) pred[edgeList[k].n] := edgeList[k].m

      done

   done



   count := count + 1

   for all vertices k in the graph, do

      if distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k),

         then return true

   done



   return false

End

 

1) Initializing the source vertex with distance to itself as 0 and all other vertices as infinity. Creating the array with size N

2) Calculate the shortest distance from the source vertex. Following this process for N-1 times where N is the number of vertices in the graph

              For relaxing the path lengths for the vertices for each edge m-n:

              if distance[n] > distance[m] + weight of edge mn, then

              distance[n] = distance[m] + weight of edge mn

3) Even after minimizing the path lengths for each vertex after N-1 times, if we can still relax the path length where distance[n] > distance[m] + weight of edge mn then we can say that the graph contains the negative edge cycle.

Therefore, the only limitation of the bellman ford algorithm is that it does not work with a graph having a negative edge cycle.  

Example:

Consider the following weighted graph

bellman ford example

Select the source vertex with path value 0 and all other vertices as infinity.

selecting the source vertex

Visit the neighbouring edge from the source vertex and relax the path length of the neighbouring vertex if the new calculated path length is smaller than the previous path length

visiting the neighbouring edge

This process must be followed N-1 times where N is the total number of vertices. This is because in the worst-case scenario any vertex’s path length can be changed to an even smaller path length for N times.

bellman ford time run complexity

Therefore after N-1 iterations, we find our new path lengths and we can check if the graph has a negative cycle or not.

final output of bellman ford

Pseudocode

function bellmanFord(G, S)

  for each vertex N in G

    distance[N] <- infinite

      previous[N] <- NULL

  distance[S] <- 0



  for each vertex N in G

    for each edge (M,N) in G

      tempDistance <- distance[M] + edge_weight(M, N)

      if tempDistance < distance[N]

        distance[N] <- tempDistance

        previous[N] <- M



  for each edge (M,N) in G

    If distance[M] + edge_weight(M, N) < distance[N}

      Error: Negative Cycle Exists



  return distance[], previous[]

 

We maintain the path length of every vertex and store that in an array with a size N where N is the number of vertices. After the algorithm is over we will backtrack from the last vertex to the source vertex to find the path.

Python Code for bellman ford algorithm

class Graph:



    def __init__(self, vertices):

        self.M = vertices   # Total number of vertices in the graph

        self.graph = []     # Array of edges



    # Add edges

    def add_edge(self, a, b, c):

        self.graph.append([a, b, c])



    # Print the solution

    def print_solution(self, distance):

        print("Vertex Distance from Source")

        for k in range(self.M):

            print("{0}\t\t{1}".format(k, distance[k]))



    def bellman_ford(self, src):



        distance = [float("Inf")] * self.M

        distance[src] = 0



        for _ in range(self.M - 1):

            for a, b, c in self.graph:

                if distance[a] != float("Inf") and distance[a] + c < distance[b]:

                    distance[b] = distance[a] + c



        for a, b, c in self.graph:

            if distance[a] != float("Inf") and distance[a] + c < distance[b]:

                print("Graph contains negative weight cycle")

                return



        self.print_solution(distance)



g = Graph(5)

g.add_edge(0, 1, 2)

g.add_edge(0, 2, 4)

g.add_edge(1, 3, 2)

g.add_edge(2, 4, 3)

g.add_edge(2, 3, 4)

g.add_edge(4, 3, -5)



g.bellman_ford(0)

 

Output

Vertex Distance from Source
0                   0 
1                   2 
2                   4 
3                   2 
4                   7 

Time Complexity

The time complexity of the bellman ford algorithm for the best case is O(E) while average-case and worst-case time complexity are O(NE) where N is the number of vertices and E is the total edges to be relaxed. Also, the space complexity of the bellman ford algorithm is O(N) because the size of the array is N.

Applications

  • Used for distance-routing protocol helping in routing the data packets on the network
  • Used in internet gateway routing protocol
  • Used in routing information protocol

Conclusion

In the above article, we studied what is Bellman-Ford algorithm and why we use it. We studied and understood the bellman ford algorithm step by step along with the example. We further learned python code and the corresponding output for finding the distance from the source vertex in a weighted graph. And lastly, we saw the time complexity for applying the algorithm and the applications which we can use in our practical life. 

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Shivali Bhadaniya
I'm Shivali Bhadaniya, a computer engineer student and technical content writer, very enthusiastic to learn and explore new technologies and looking towards great opportunities. It is amazing for me to share my knowledge through my content to help curious minds.