Bellman-Ford computes shortest paths from a single source in a weighted graph, including graphs with negative-weight edges. It relaxes all edges V-1 times. If any distance can still be reduced after V-1 iterations, a negative cycle exists. It is slower than Dijkstra but handles negative weights.
vector<int> bellmanFord(int n, vector<tuple<int,int,int>>& edges, int src) {
vector<int> dist(n, INT_MAX);
dist[src]=0;
for (int i=0;i<n-1;i++)
for (auto [u,v,w]:edges)
if (dist[u]!=INT_MAX && dist[u]+w<dist[v]) dist[v]=dist[u]+w;
for (auto [u,v,w]:edges)
if (dist[u]!=INT_MAX && dist[u]+w<dist[v]) return {}; // negative cycle
return dist;
}A shortest path in a graph with V vertices has at most V-1 edges. So relaxing all edges V-1 times guarantees every shortest path is found, even through intermediate nodes.
After V-1 iterations, do one more pass. If any edge can still be relaxed, a negative cycle exists (reachable from source). The algorithm reports this correctly.
Bellman-Ford is O(VE) vs Dijkstra O((V+E) log V). Dijkstra is faster but requires non-negative weights. Bellman-Ford handles negative weights and detects negative cycles.
Quiz coming soon for this algorithm.