What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Bellman Ford Algorithm in Python (Example with Code)

  • Jun 10, 2023
  • 7 Minutes Read
  • Why Trust Us
    We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
  • By Shivali Bhadaniya
 Bellman Ford Algorithm in Python (Example with Code)

Bellman-Ford algorithm stands as a fundamental tool for finding the shortest paths between nodes. Richard Bellman and Lester Ford Jr. founded this algorithm has found applications in computer science. In this article, we will study the Bellman-Ford algorithm along with its code in Python. We will also find its time complexity.

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 Bbellman-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 neighbor vertex in each iteration but the bellman ford algorithm visits each vertex through each edge in every iteration.

Apart from Bellman-Ford and Dijkstra's, Floyd Warshall Algorithm is also the shortest path algorithm. But the 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.

Here is the simple algorithm:


   count := 1

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

   for all vertices n of the graph, do

      distance[n] := 

      pred[n] := ?


   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



   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


   return false



Let's look at it step-by-step to understand the Bellman-Ford algorithm:

  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.
    1. For relaxing the path lengths for the vertices for each edge m-n:
    2. if distance[n] > distance[m] + weight of edge mn, then
    3. 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.

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. 

Bellman-Ford Algorithm 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 neighboring edge from the source vertex and relax the path length of the neighboring vertex if the newly 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

Look at the following 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

Here is the full source code to implement the Bellman-Ford algorithm in Python:

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")



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)




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.

Is Bellman-Ford better than Dijkstra?

Like everything else, Bellman-Ford and Dijkstra have their own use cases and pros and cons.

The Bellman-Ford algorithm is better in cases where the graph contains non-negative weighted edges. It is designed to handle negative weight edges and can detect negative weight cycles.

This method has a way of handling negative weight edges, but it has a higher time complexity of O(|V|*|E|), where |V| is the number of vertices and |E| is the number of edges.  However, in terms of time complexity, Bellman-Ford is less efficient.

On the other hand, for a graph with non-negative edge weights, Dijkstra’s algorithm is a better choice, because it is faster and has better time efficiency. Its time complexity is O((|V| + |E|)log|V|) when using a binary heap priority queue or O(|V|^2) when using a simple array.

Dijkstra’s algorithm is more time efficient because it discards all the paths which are not optimal, ensuring that it takes the shortest possible path.

Where does the Bellman-Ford algorithm fail?

The main purpose of this algorithm is to find the shortest possible path. The presence of a negative-weight cycle can cause the Bellman-Ford algorithm to fail. A negative weight cycle is a cycle in the graph that sums up to a negative weight when the weights of all its edges are added up.

Another case would be if the given graph has no edges since the Bellman-Ford algorithm relies solely on the edges to determine the shortest path. If the graph is a disconnected graph, i.e., if there are no nodes connecting two vertices, the algorithm will malfunction.


In the above article, we studied what is Bellman-Ford algorithm, 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.

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.