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 fromu
tov
. -
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