Shortest Path Bellman-Ford
In this page:
What is Bellman-Ford
Bellman-Ford also finds shortest paths from a single source, but unlike Dijkstra it tolerates negative edge weights — useful when some edges represent gains rather than costs, like currency arbitrage or refund scenarios.
Example: What is Bellman-Ford
#include <iostream>
using namespace std;
int main() {
int edges[][3] = {{0,1,5},{1,2,-3}};
cout << "Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] edges = {{0,1,5},{1,2,-3}};
System.out.println("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not");
}
}edges = [(0,1,5),(1,2,-3)]
print("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not")#include <stdio.h>
int main() {
int edges[2][3] = {{0,1,5},{1,2,-3}};
printf("Edge weight -3 present: Bellman-Ford handles it, Dijkstra would not");
return 0;
}Login to try C/C++/Java code in the editor
Relax Edges
Instead of greedily finalizing vertices, it relaxes every single edge in the graph, once per pass, letting shorter paths propagate gradually across multiple rounds until no distance can be improved further.
Example: Relax Edges
#include <iostream>
using namespace std;
int main() {
int dist[3] = {0, 1000000, 1000000};
int edges[2][3] = {{0,1,4},{1,2,-2}};
for (int pass = 0; pass < 2; pass++)
for (auto& e : edges)
if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
cout << "After relaxing all edges twice, dist[2] = " << dist[2];
return 0;
}public class Main {
public static void main(String[] args) {
int[] dist = {0, 1000000, 1000000};
int[][] edges = {{0,1,4},{1,2,-2}};
for (int pass = 0; pass < 2; pass++)
for (int[] e : edges)
if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
System.out.println("After relaxing all edges twice, dist[2] = " + dist[2]);
}
}dist = [0, 1000000, 1000000]
edges = [(0,1,4),(1,2,-2)]
for _ in range(2):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
print("After relaxing all edges twice, dist[2] =", dist[2])#include <stdio.h>
int main() {
int dist[3] = {0, 1000000, 1000000};
int edges[2][3] = {{0,1,4},{1,2,-2}};
for (int pass = 0; pass < 2; pass++)
for (int i = 0; i < 2; i++)
if (dist[edges[i][0]] + edges[i][2] < dist[edges[i][1]])
dist[edges[i][1]] = dist[edges[i][0]] + edges[i][2];
printf("After relaxing all edges twice, dist[2] = %d", dist[2]);
return 0;
}Login to try C/C++/Java code in the editor
Negative Weights
Because the algorithm doesn't assume any weight is non-negative, it can correctly shorten a path even when doing so means temporarily using an edge that reduces the running total.
Example: Negative Weights
#include <iostream>
using namespace std;
int main() {
int dist[2] = {0, 10};
int weight = -7;
if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; cout << "Shortened via negative edge to " << dist[1]; }
return 0;
}public class Main {
public static void main(String[] args) {
int[] dist = {0, 10};
int weight = -7;
if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; System.out.println("Shortened via negative edge to " + dist[1]); }
}
}dist = [0, 10]
weight = -7
if dist[0] + weight < dist[1]:
dist[1] = dist[0] + weight
print("Shortened via negative edge to", dist[1])#include <stdio.h>
int main() {
int dist[2] = {0, 10};
int weight = -7;
if (dist[0] + weight < dist[1]) { dist[1] = dist[0] + weight; printf("Shortened via negative edge to %d", dist[1]); }
return 0;
}Login to try C/C++/Java code in the editor
Negative Cycle
A shortest path in a graph with V vertices can use at most V-1 edges, so if a distance can still be improved after V-1 full passes, that improvement can only be explained by an edge weight that loses value indefinitely around a cycle — a negative cycle, which the extra pass exposes.
Example: Negative Cycle
#include <iostream>
using namespace std;
int main() {
int V = 4;
bool improvedOnPassV = true;
if (improvedOnPassV) cout << "Distance still improved after " << V-1 << " passes: negative cycle detected";
return 0;
}public class Main {
public static void main(String[] args) {
int V = 4;
boolean improvedOnPassV = true;
if (improvedOnPassV) System.out.println("Distance still improved after " + (V-1) + " passes: negative cycle detected");
}
}V = 4
improved_on_pass_v = True
if improved_on_pass_v:
print(f"Distance still improved after {V-1} passes: negative cycle detected")#include <stdio.h>
int main() {
int V = 4;
int improvedOnPassV = 1;
if (improvedOnPassV) printf("Distance still improved after %d passes: negative cycle detected", V-1);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Relaxing every edge once takes O(E) time, and the algorithm repeats that for up to V-1 passes, giving O(VE) overall — slower than Dijkstra's algorithm, but the price for handling negative weights safely.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely");
}
}print("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely")#include <stdio.h>
int main() {
printf("Bellman-Ford: O(V*E), slower than Dijkstra but handles negative weights safely");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: