Bellman Ford Algorithm in detail with code

Board Infinity
Board Infinity
Bellman Ford Algorithm in detail with code

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?


Introduction

In this article you will understand the Bellman-Ford algorithm step-by-step, using the example as a guide. C++ implementation with the code for calculating the distance from the source vertex in a weighted graph is also covered in this article.

Approach

The Bellman-Ford algorithm imitates the shortest routes in a weighted digraph from a single site vertex to all other vertices. Since it can handle graphs with certain edge weights that are negative values, it is more flexible than Dijkstra's method for the identical issue. The Bellman-Ford algorithm makes use of dynamic programming. It starts with a beginning vertex and determines the shortest paths an edge can take to reach additional vertices. The process then continues in search of a path with two edges. The bottom-up method is employed by the Bellman-Ford algorithm.

Negative Cycles

Negative weight edges can produce negative weight cycles that, by going back to the same location, shorten the overall path length. Negative weight cycles could provide the wrong answer while trying to identify the shortest path. Because they may experience a negative weight cycle that shortens the trip, shortest path methods like Dijkstra's Algorithm that cannot identify such a cycle may generate inaccurate results.

Steps

  • Step 1: Make a list of every edge in the graph. If the graph is represented as an adjacency list, then this is easy.
  • Step 2: The number of iterations is calculated using the formula "V - 1". The number of iterations will grow the same number of vertices since the shortest path to an edge can only be changed V - 1 times.
  • Step 3: Start with a random vertex at a distance of 0 minimum. You are overstating the real lengths, hence all other nodes ought to be given a distance of infinite. Relax the vertices' route lengths for each edge u-v:
  • Distance[v] = distance[u] + edge weight uv if distance[v] is larger than distance[u] + edge weight uv.
  • Step 4: Alter the distance for each Edge in every iteration if the new distance is smaller than the old one. The distance covered from the beginning node to each individual node is the distance to each node.
  • Step 5: You must take alliterations into account to make sure all potential pathways are taken into account. If you accomplish this, the distance you have traveled will be the shortest.

Code

#include <bits/stdc++.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
   struct Graph* graph = new Graph;
   graph->V = V;
   graph->E = E;
   graph->edge = new Edge[E];
   return graph;
}
void BellmanFord(struct Graph* graph, int src) {
   int V = graph->V;
   int E = graph->E;
   int dist[V];
   for (int i = 0; i < V; i++)
      dist[i] = INT_MAX;
      dist[src] = 0;
   for (int i = 1; i <= V - 1; i++) {
      for (int j = 0; j < E; j++) {
         int u = graph->edge[j].src;
         int v = graph->edge[j].dest;
         int weight = graph->edge[j].weight;
         if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
         dist[v] = dist[u] + weight;
      }
   }
   for (int i = 0; i < E; i++) {
      int u = graph->edge[i].src;
      int v = graph->edge[i].dest;
      int weight = graph->edge[i].weight;
      if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
         printf("Graph contains negative weight cycle");
         return;
      }
   }
   printf("Vertex :\t\t\t ");
   for (int i = 0; i < V; ++i)
      printf("%d \t", i);
      printf("\nDistance (from the source): ");
   for (int i = 0; i < V; ++i)
      printf("%d \t",dist[i]);
   return;
}
int main() {
   int V = 5;
   int E = 8;
   struct Graph* 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);
   return 0;
}



write your code here: Coding Playground

Output:

Vertex : 0 1 2 3 4

Distance (from the source)

Complexity Analysis

The graph might present a worst-case scenario when you encounter a negative cycle. You would need to relax |E| * (|E| - 1) / 2 edges, (|V| - 1) number of times in a full graph with edges connecting every pair of vertices, assuming you identified the shortest route in the first few iterations or repetitions but continued with edge relaxation.

The complete graph will lead to the worst case scenario where the time complexity will be:

O(|V|^2) = O(E V). O(|V|) = O (V^3)

Applications of Bellman Ford Algorithm

  1. Finding weight-loss relapse cycles
  2. Calculate the least amount of heat that can acquire or lose during a chemical process.
  3. Figuring out the most effective currency conversion technique. looking at a graph to see if there are any negative weight cycles.
  4. Find the graph's shortest route using negative weights.
  5. In data networks, the idea of routing is applied.