HomeResourcesSoftware DevelopmentData Structure Tutorial for BeginnersBellman-Ford Algorithm: Pseudocode, Time Complexity and Examples

Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best and Easiest Way to Understand an Algorithm

Lesson - 21

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 22

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 23

A One-Stop Solution Guide to Understand Data Structure and Algorithm Complexity

Lesson - 24

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 25

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 26

What Is Selection Sort Algorithm In Data Structures?

Lesson - 27

Everything You Need to Know About Radix Sort Algorithm

Lesson - 28

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 29

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 30

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 31

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 32

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 33

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 34

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 35

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 36

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 37

Your One-Stop Solution for Graphs in Data Structures

Lesson - 38

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 39

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 40

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 41

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 42

The Holistic Look at Longest Common Subsequence Problem

Lesson - 43

The Best Article to Understand What Is Dynamic Programming

Lesson - 44

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 45

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 46

One Stop Solution to All the Dynamic Programming Problems

Lesson - 47

Understanding the Fundamentals of Binomial Distribution

Lesson - 48

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 49

Understanding the Difference Between Array and Linked List

Lesson - 50

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 51

A Comprehensive Look at Queue in Data Structure

Lesson - 52

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 53

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 54

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 55

The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

Lesson - 56

All You Need to Know About How to Create a React JS Portfolio Project

Lesson - 57

The Best Guide to Learn How to Make a Wireframe: What is a Wireframe?

Lesson - 58

The Best DSA Projects for Your Resume

Lesson - 59

Top 5 Best Coding Books You Must Read

Lesson - 60

The Working and Implementation of Physical Layer in the OSI Model

Lesson - 61

How to Create an Instagram Clone Using React?

Lesson - 62

ReactJS Vs VueJS

Lesson - 63

Bellman-Ford Algorithm: Pseudocode, Time Complexity and Examples

Lesson 37 of 63

By Soni UpadhyayLast updated on Feb 13, 202368861
The Fundamentals of the Bellman-Ford Algorithm

Table of Contents

View More

The Bellman-Ford algorithm emulates the shortest paths from a single source vertex to all other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem but more versatile because it can handle graphs with some edge weights that are negative numbers. Alfonso Shimbel proposed the algorithm in 1955, but it is now named after Richard Bellman and Lester Ford Jr., who brought it out in 1958 and 1956. In 1959, Edward F. Moore published a variation of the algorithm, sometimes referred to as the Bellman-Ford–Moore algorithm.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

What Is the Bellman-Ford Algorithm?

Dynamic Programming is used in the Bellman-Ford algorithm. It begins with a starting vertex and calculates the distances between other vertices that a single edge can reach. It then searches for a path with two edges, and so on. The Bellman-Ford algorithm uses the bottom-up approach.

what-is-bellman-ford-algorithm.

Based on the "Principle of Relaxation," more accurate values gradually recovered an approximation to the proper distance until finally reaching the optimum solution.

Negative weight edges can generate negative weight cycles, which reduce the total path distance by returning to the same point.

Why Should You Be Cautious With Negative Weights?

When attempting to find the shortest path, negative weight cycles may produce an incorrect result.

Shortest path algorithms, such as Dijkstra's Algorithm that cannot detect such a cycle, may produce incorrect results because they may go through a negative weight cycle, reducing the path length.

After learning about the Bellman-Ford algorithm, you will look at how it works in this tutorial.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

How Does the Bellman-Ford Algorithm Work?

The Bellman-Ford algorithm works by grossly underestimating the length of the path from the starting vertex to all other vertices. The algorithm then iteratively relaxes those estimates by discovering new ways that are shorter than the previously overestimated paths.

You can ensure that the result is optimized by repeating this process for all vertices.

Step 1: Make a list of all the graph's edges. This is simple if an adjacency list represents the graph.

Step 2: "V - 1" is used to calculate the number of iterations. Because the shortest distance to an edge can be adjusted V - 1 time at most, the number of iterations will increase the same number of vertices.

Step 3: Begin with an arbitrary vertex and a minimum distance of zero. Because you are exaggerating the actual distances, all other nodes should be assigned infinity.

For each edge u-v, relax the path lengths for the vertices:

If distance[v] is greater than distance[u] + edge weight uv, then

distance[v] = distance[u] + edge weight uv

Step 4:If the new distance is less than the previous one, update the distance for each Edge in each iteration. The distance to each node is the total distance from the starting node to this specific node.

Step 5: To ensure that all possible paths are considered, you must consider alliterations. You will end up with the shortest distance if you do this.

Moving ahead with this tutorial on the Bellman-Ford algorithm, you will now learn the pseudocode for this algorithm.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

Pseudocode of the Bellman-Ford Algorithm

Every Vertex's path distance must be maintained. That can be stored in a V-dimensional array, where V is the number of vertices.

Not only do you need to know the length of the shortest path, but you also need to be able to find it. To accomplish this, you must map each Vertex to the Vertex that most recently updated its path length.

When the algorithm is finished, you can find the path from the destination vertex to the source.

function bellmanFordAlgorithm(G, s) //G is the graph and s is the source vertex

  for each vertex V in G

    dist[V] <- infinite // dist is distance

      prev[V] <- NULL // prev is previous

  dist[s] <- 0

  for each vertex V in G

    for each edge (u,v) in G

      temporaryDist <- dist[u] + edgeweight(u, v)

      if temporaryDist < dist[v]

        dist[v] <- temporaryDist

        prev[v] <- u 

  for each edge (U,V) in G

    If dist[U] + edgeweight(U, V) < dist[V}

      Error: Negative Cycle Exists

  return dist[], previ[]

As you progress through this tutorial, you will see an example of the Bellman-Ford algorithm for a better learning experience.

An Example of Bellman-Ford Algorithm

Consider the weighted graph below.

Example-of-bellman-ford-algorithm.

  • Choose path value 0 for the source vertex and infinity for all other vertices.

Example-of-bellman-ford-algorithm1.

  • If the new calculated path length is less than the previous path length, go to the source vertex's neighboring Edge and relax the path length of the adjacent Vertex.

Example-of-bellman-ford-algorithm2.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

  • This procedure must be repeated V-1 times, where V is the number of vertices in total. This happened because, in the worst-case scenario, any vertex's path length can be changed N times to an even shorter path length.

Example-of-bellman-ford-algorithm3.

Example-of-bellman-ford-algorithm3

  • As a result, after V-1 iterations, you find your new path lengths and can determine in case the graph has a negative cycle or not.

Example-of-bellman-ford-algorithm5

You will now look at the time and space complexity of the Bellman-Ford algorithm after you have a better understanding of it.

The Complexity of Bellman-Ford Algorithm

Following is the time complexity of the bellman ford algorithm 

For all cases, the complexity of this algorithm will be determined by the number of edge comparisons.

if temporaryDist < dist[v]

Edge relaxation differences depend on the graph and the sequence of looking in on edges in the graph.

The algorithm may need to undergo all repetitions while updating edges, but in many cases, the result is obtained in the first few iterations, so no updates are required.

dist[v] <- temporaryDist

  • Worst-Case Time Complexity

When you come across a negative cycle in the graph, you can have a worst-case scenario.

As an example of a negative cycle, consider the following:

worst-case-bellman-ford-algorithm.

In a complete graph with edges between every pair of vertices, and assuming you found the shortest path in the first few iterations or repetitions but still go on with edge relaxation, you would have to relax |E| * (|E| - 1) / 2 edges, (|V| - 1) number of times.

The worst-case scenario in the case of a complete graph, the time complexity is as follows:

O(|V|2) = O(E V). O(|V|) = O (V3)

  • Average Case Time Complexity

You can reduce the worst-case running time by stopping the algorithm when no changes are made to the path values. As a result, there will be fewer iterations.

Another way to improve it is to ignore any vertex V with a distance value that has not changed since the last relaxation in subsequent iterations, reducing the number of edges that need to be relaxed and increasing the number of edges with correct values after each iteration. More information is available at the link at the bottom of this post.

Relaxation occurs |V| - 1 time for every |E| the number of edges, so you multiply the two and get the average, which is the quadratic time complexity of O. (E V).

Automation Test Engineer Master's Program

To learn about the automation of web applicationsExplore Course
Automation Test Engineer Master's Program

  • Best Case Time Complexity

best-case-time-complexity-in-bellman-ford-algorithm

If edge relaxation occurs from left to right in the above graph, the algorithm would only need to perform one relaxation iteration to find the shortest path, resulting in the time complexity of O(E) corresponding to the number of edges in the graph.

The following is the space complexity of the bellman ford algorithm:

The space complexity of the Bellman-Ford algorithm is O(V).

Following that, in this Bellman-Ford algorithm tutorial, you will look at some use cases of the Bellman-Ford algorithm.

Uses of Bellman-Ford Algorithm

There are several real-world applications for the Bellman-Ford algorithm, including:

  • Identifying negative weight cycles
  • In a chemical reaction, calculate the smallest possible heat gain/loss.
  • Identifying the most efficient currency conversion method.

You will now peek at some applications of the Bellman-Ford algorithm in this tutorial.

Applications of the Bellman-Ford Algorithm

Following are the applications of the bellman ford algorithm:

  • Examining a graph for the presence of negative weight cycles.
  • Using negative weights, find the shortest path in a graph.
  • Routing is a concept used in data networks.

Last but not least, you will need to perform practical demonstrations of the Bellman-Ford algorithm in the C programming language.

 Code Demonstration of Bellman-Ford Algorithm

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<string.h>

#include<limits.h>

struct Edges

{

    // This structure is equal to an edge. Edge contains two endpoints. These edges are directed edges so they

//contain source and destination and some weight. These 3 are elements in this structure

    int src, dest, wt;

};

// a structure to represent a graph

struct Graph

{

    int Vertex, Edge;

//Vertex is the number of vertices, and Edge is the number of edges

    struct Edges* edge;

// This structure contains another structure that we have already created.

};

struct Graph* designGraph(int Vertex, int Edge)

{

    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));

//Allocating space to structure graph

    graph->Vertex = Vertex; //assigning values to structure elements that taken form user.

    graph->Edge = Edge;

    graph->edge = (struct Edges*) malloc( graph->Edge * sizeof( struct Edges ) );

//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges 

    return graph;

}

void Solution(int dist[], int n)

{

// This function prints the last solution

    printf("\nVertex\tDistance from Source Vertex\n");

    int i;

    for (i = 0; i < n; ++i){

printf("%d \t\t %d\n", i, dist[i]);

}

}

void BellmanFordalgorithm(struct Graph* graph, int src)

{

    int Vertex = graph->Vertex;

    int Edge = graph->Edge;

    int Distance[Vertex];

    int i,j;

    // This is the initial step that we know, and we initialize all distances to infinity except the source vertex.

// We assign source distance as 0

    for (i = 0; i < Vertex; i++)

        Distance[i] = INT_MAX;

    Distance[src] = 0;

    //The shortest path of graph that contain Vertex vertices, never contain "Veretx-1" edges. So we do here "Vertex-1" relaxations

    for (i = 1; i <= Vertex-1; i++)

    {

        for (j = 0; j < Edge; j++)

        {

            int u = graph->edge[j].src; 

            int v = graph->edge[j].dest;

            int wt = graph->edge[j].wt;

            if (Distance[u] + wt < Distance[v])

                Distance[v] = Distance[u] + wt;

        }

    }

    //, up to now, the shortest path found. But BellmanFordalgorithm checks for negative edge cycles. In this step, we check for that

    // shortest path if the graph doesn't contain any negative weight cycle in the graph.

    // If we get a shorter path, then there is a negative edge cycle.

    for (i = 0; i < Edge; i++)

    {

        int u = graph->edge[i].src;

        int v = graph->edge[i].dest;

        int wt = graph->edge[i].wt;

        if (Distance[u] + wt < Distance[v])

            printf("This graph contains negative edge cycle\n");

    } 

    Solution(Distance, Vertex);

    return;

}

int main()

{

    int V,E,S; //V = no.of Vertices, E = no.of Edges, S is source vertex

printf("Enter number of vertices\n");

    scanf("%d",&V);

printf("Enter number of edges\n");

    scanf("%d",&E);

printf("Enter the source vertex number\n");

scanf("%d",&S);

    struct Graph* graph = designGraph(V, E); //calling the function to allocate space to these many vertices and edges

    int i;

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

        printf("\nEnter edge %d properties Source, destination, weight respectively\n",i+1);

        scanf("%d",&graph->edge[i].src);

        scanf("%d",&graph->edge[i].dest);

        scanf("%d",&graph->edge[i].wt);

    }

    BellmanFordalgorithm(graph, S);

//passing created graph and source vertex to BellmanFord Algorithm function

    return 0;

}

Output

bellman-ford-algorithm-code-output

Now that you have reached the end of the Bellman-Ford tutorial, you will go over everything you’ve learned so far.

Advance your career as a MEAN stack developer with the Post Graduate Program In Full Stack Web Development. Enroll now!

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

Next Steps

In this Bellman-Ford algorithm tutorial, you looked at what the algorithm is and how it works. You studied and comprehended the Bellman-Ford algorithm step-by-step, using the example as a guide. You also learned C programming language code and the output for calculating the distance from the source vertex in a weighted graph. And you saw the time complexity for applying the algorithm and the applications and uses that you can put to use in your daily lives.

Assume you're looking for a more in-depth study that goes beyond Mobile and Software Development and covers today's most in-demand programming languages and skills. In that case, Simplilearn's software-development course is the right choice for you. Explore this globally recognized Bootcamp program. Rest assured that completing it will be the best decision you can make to enter and advance in the mobile and software development professions.

Do you have any queries about this tutorial on Bellman-Ford Algorithm? Please leave them in the comments section at the bottom of this page if you do. Our experts will be happy to respond to your questions as earliest as possible!

About the Author

Soni UpadhyaySoni Upadhyay

Soni Upadhyay is with Simplilearn's Research Analysis Team. She's a Computer Science and Engineering graduate. Programming languages are her area of expertise. She has a brilliant knowledge of C, C++, and Java Programming languages

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, OPM3 and the PMI ATP seal are the registered marks of the Project Management Institute, Inc.