Bellman-Ford Algorithm in C++ – Shortest Path with Negative Weights

The Bellman-Ford algorithm is a classical approach for finding the shortest path from a single source node to all other vertices in a weighted graph, even when the graph contains negative weight edges. Unlike Dijkstra’s algorithm, Bellman-Ford is capable of detecting negative weight cycles.In this post, we implement Bellman-Ford using a simple nested loop structure, exactly as used in competitive programming and system-level applications.

Bellman-Ford Algorithm in C++ – Shortest Path with Negative Weights

// User function Template for C++

class Solution {
  public:
    vector<int> bellmanFord(int V, vector<vector<int>>& edges, int src) {
        // Code here
        vector<int> t(V,1e8);
        t[src]=0;
        for(int i=0;i<V-1;i++){
            for(int j=0;j<edges.size();j++){
                int u=edges[j][0];
                int v=edges[j][1];
                int cost=edges[j][2];
                if(t[u]!=1e8 && t[u]+cost<t[v]){
                    t[v]=t[u]+cost;
                }
            }
        }
        for(int i=0;i<edges.size();i++){
                int u=edges[i][0];
                int v=edges[i][1];
                int cost=edges[i][2];
                if(t[u]!=1e8 && t[u]+cost<t[v]){
                    return {-1};
                }
        }
        return t;
    }
};

Input Format

• V: Total number of vertices in the graph.

• edges: Each element is a vector {u, v, weight} representing a directed edge from u to v.

• src: The source node from which the shortest paths are calculated.

Output

• If no negative weight cycle exists, it returns a vector of shortest distances from the source node to all others.

• If a negative weight cycle is detected, returns {-1}.

Sample Input
V = 5
edges = {
{0, 1, -1},
{0, 2, 4},
{1, 2, 3},
{1, 3, 2},
{1, 4, 2},
{3, 2, 5},
{3, 1, 1},
{4, 3, -3}
}
src = 0
Sample Output
0 -1 2 -2 1