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?

1

Initialize distances.

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

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
3

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<<" ";
    }
}
}

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)