Bellman-Ford Algorithm

Algorithm for finding the shortest path from a source to all vertices, even with negative weight edges

Introduction

Bellman Ford Algorithm is a single-source shortest path algorithm that finds the shortest paths from a source vertex to all other vertices in a weighted graph even with graphs containing negative weight edges, unlike Dijkstra's algorithm. It works by repeatedly relaxing all edges to update the shortest distances. Unlike Dijkstra's algorithm, Bellman-Ford can detect negative weight cycles, making it useful for graphs with negative edges.

How Bellman Ford Algorithm Works?

Initialize distances.

Set the distance to the source vertex as 0.
Set all other distances as infinity.

Relax all edges (V-1 times).

Loop through all edges and update the distance of the destination vertex if a shorter path is found. Relaxation: distance[v]=distance[u]+weight

Check for negative weight cycles.

If we can still relax any edge after (V-1) iterations, there is a negative weight cycle.

Implementation of Bellman Ford Algorithm

//bellmanford-algo.cpp
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int vertex, edge;
    cin >> vertex >> edge;
    vector<vector<int>> adjlist;
    int u, v, wt;
    for (int i = 0; i < vertex; i++)
    {
        cin >> u >> v >> wt;
        adjlist.push_back({u,v,wt});
    }
    vector<int> dist(vertex,INT_MAX);
    dist[0]=0;
    for(int i=0;i<vertex-1;i++){
        for(int j=0;j<edge;j++){
            int u=adjlist[j][0];
            int v=adjlist[j][1];
            int wt=adjlist[j][2];
            if(dist[u]==INT_MAX) continue;
            if(dist[u]+wt<dist[v]){
                dist[v]=dist[u]+wt;
            }
        }
    }
    bool flag=false;
    for(int j=0;j<edge;j++){
        int u=adjlist[j][0];
        int v=adjlist[j][1];
        int wt=adjlist[j][2];
        if(dist[u]==INT_MAX) continue;
        if(dist[u]+wt<dist[v]){
            flag=true;
            break;
        }
    }
    if(flag){
        cout<<"Negative Cycle Detected";
    }
    else{
        for(int &ele:dist){
            cout<<ele<<" ";
        }
    }
}

# bellmanford-algo.py
def bellman_ford(vertices, edges, source):
    # Initialize distances
    dist = [float('inf')] * vertices
    dist[source] = 0
    
    # Relax edges V-1 times
    for _ in range(vertices - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # Check for negative cycles
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return "Negative Cycle Detected"
    
    return dist

# Example usage
if __name__ == "__main__":
    vertices = 5
    edges = [(0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2), (3, 2, 5), (3, 1, 1), (4, 3, -3)]
    source = 0
    
    result = bellman_ford(vertices, edges, source)
    print(result)

//bellmanford-algo.js
function bellmanFord(vertices, edges, source) {
    // Initialize distances
    const dist = new Array(vertices).fill(Infinity);
    dist[source] = 0;
    
    // Relax edges V-1 times
    for (let i = 0; i < vertices - 1; i++) {
        for (const [u, v, weight] of edges) {
            if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // Check for negative cycles
    for (const [u, v, weight] of edges) {
        if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
            return "Negative Cycle Detected";
        }
    }
    
    return dist;
}

// Example usage
const vertices = 5;
const edges = [[0, 1, -1], [0, 2, 4], [1, 2, 3], [1, 3, 2], [3, 2, 5], [3, 1, 1], [4, 3, -3]];
const source = 0;

const result = bellmanFord(vertices, edges, source);
console.log(result);

Time Complexity

Relaxation Loop: O(V−1) × O(E) = O(VE)
Negative Cycle Detection: O(E)
Overall Time Complexity: O(VE)

Space Complexity

Graph Representation: O(E)
Distance Array: O(V)
Overall Space Complexity: O(V+E)

Bellman-Ford Algorithm

On this page