The Bellman-Ford algorithm is a popular shortest path algorithm that is used to find the shortest path from a source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford could also be used when there are negative edge weights.

Bellman-Ford Algorithm is also used to detect if there is a negative-weight cycle in the graph. If such a cycle exists, it indicates that no solution for “single-source shortest path” exists. However, if there is no negative-weight cycle it returns the shortest paths and their weights.

This algorithm uses **Relaxation**, to find the shortest path between the source vertex and other vertices. It gradually expands the search space until the shortest path to the destination node is found.

**Relaxation (Pseudocode)**

Consider the below pseudocode for `Graph G`

and `source vertex s`

Initialize (G, s) for each v ∈ G[vertices]: distance[v] = INF distance[s] = 0 Relax () if distance[v] > distance[u] + edge_weight[u, v]: distance[v] = distance[u] + edge_weight[u, v]

###### Bellman-Ford Algorithm

**Explanation**

- Initialize the
`weighted-graph G`

and assign initial`distance[]`

to all nodes. Set the distance of the source node as`0`

and all other nodes as`infinity`

. - Perform
`V - 1`

iterations, where`V`

is the number of vertices. - For each iteration, iterate through all the edges in the graph and relax them if a shorter path is found.
- After the
`V - 1`

iterations, check for negative cycles. If there is a negative cycle, it means there is no shortest path, as the distance can keep decreasing indefinitely. - If there are no negative cycles, the
`distance[]`

array will contain the shortest paths from the source vertex to all other vertices.

###### Bellman-Ford Limitations

**Time Complexity**: The worst-case time complexity of the Bellman-Ford algorithm is O(V * E), where V is the number of vertices and E is the number of edges in the graph. This makes it less efficient compared to some other shortest path algorithms like Dijkstra’s algorithm. In cases where there’s a dense graph such that E =^{v}C_{2}(Combinatorics), time complexity becomes O(V^{3}).**Negative Cycles**: If the graph contains a negative cycle, the Bellman-Ford algorithm cannot produce correct results. It will keep updating the distances of the vertices indefinitely, as negative cycles allow for continuously decreasing path weights.

**Pseudocode**

Bellman-Ford (G, s) Initialize (G, s) for i = 1 to G[vertices]-1 for each edge ∈ G[edges]: if distance[v] > distance[u] + edge_weight[u, v]: distance[v] = distance[u] + edge_weight[u, v] for each edge ∈ G[edges]: if distance[v] > distance[u] + edge_weight[u, v]: return false return true

**Code Implementation**

```
//
// main.cpp
// Bellman Ford Algorithm
//
// Created by Himanshu on 28/05/23.
//
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
#define INF numeric_limits<int>::max()
struct Edge {
int source, destination, weight;
};
void printDistances(vector<int> distance, int V, int source) {
// Print the shortest distances
for (int i = 0; i < V; ++i) {
cout<<"Shortest distance from source ("<< source<<") to vertex "<<i<<": ";
if (distance[i] == INF) {
cout<<"INF"<<endl;
} else {
cout<<distance[i]<<endl;
}
}
}
bool BellmanFord (vector<Edge> &edges, vector<int> &distance, int V, int source) {
distance[source] = 0;
// Relax edges V-1 times
for (int i = 0; i < V - 1; ++i) {
for (const auto& edge : edges) {
int u = edge.source;
int v = edge.destination;
int weight = edge.weight;
if (distance[u] != INF && ((distance[u] + weight) < distance[v])) {
distance[v] = distance[u] + weight;
}
}
}
// Check for negative cycles
for (const auto& edge : edges) {
int u = edge.source;
int v = edge.destination;
int weight = edge.weight;
if (distance[u] != INF && ((distance[u] + weight) < distance[v])) {
return false;
}
}
return true;
}
int main() {
int V = 5; // Number of vertices
vector<Edge> edges = {
{0, 1, 6},
{0, 2, 7},
{1, 2, 8},
{1, 3, -4},
{1, 4, 5},
{2, 3, 9},
{2, 4, -3},
{3, 0, 2},
{3, 4, 7},
{4, 1, -2}
};
vector<int> distance(V, INF);
int source = 0; // Source vertex
if (!BellmanFord(edges, distance, V, source)) {
cout<<"Graph has negative cycle!"<<endl;
} else {
printDistances(distance, V, source);
}
return 0;
}
```

**Output**

Shortest distance from source (0) to vertex 0: 0 Shortest distance from source (0) to vertex 1: 2 Shortest distance from source (0) to vertex 2: 7 Shortest distance from source (0) to vertex 3: -2 Shortest distance from source (0) to vertex 4: 4

**Time complexity: O(V . E)**