Bellman-Ford Algorithm | Single source shortest path

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

1. 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.
2. Perform V - 1 iterations, where V is the number of vertices.
3. For each iteration, iterate through all the edges in the graph and relax them if a shorter path is found.
4. 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.
5. 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 = ^vC₂ (Combinatorics), time complexity becomes O(V³).
• 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)