Bellman-Ford Algorithm
Graph Selection
Playback Controls
Select start and target nodes to begin
Bellman-Ford Info
Key Features:
- • Handles negative edge weights
- • Detects negative cycles
- • Time complexity: O(V×E)
- • More general than Dijkstra
Legend:
Reference implementation of Bellman-Ford Algorithm. Select a language tab to view and copy the code.
#include <limits.h>
#define V 5
#define E 8
typedef struct { int u, v, w; } Edge;
void bellman_ford(Edge edges[], int num_e, int src) {
int dist[V];
for (int i = 0; i < V; i++) dist[i] = INT_MAX;
dist[src] = 0;
/* Relax all edges V-1 times */
for (int i = 1; i <= V - 1; i++)
for (int j = 0; j < num_e; j++) {
int u = edges[j].u, v = edges[j].v, w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
/* Detect negative-weight cycles */
for (int j = 0; j < num_e; j++) {
int u = edges[j].u, v = edges[j].v, w = edges[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
printf("Negative cycle detected\n");
}
}#include <vector>
#include <limits>
#include <stdexcept>
struct Edge { int u, v, w; };
std::vector<int> bellmanFord(int n, const std::vector<Edge>& edges, int src) {
std::vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int i = 1; i <= n - 1; i++)
for (const auto& e : edges)
if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
dist[e.v] = dist[e.u] + e.w;
for (const auto& e : edges)
if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
throw std::runtime_error("Negative weight cycle detected");
return dist;
}import java.util.Arrays;
public static int[] bellmanFord(int n, int[][] edges, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Relax all edges n-1 times
for (int i = 1; i <= n - 1; i++)
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
// Negative-cycle check
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
throw new IllegalStateException("Negative weight cycle");
}
return dist;
}def bellman_ford(n: int, edges: list[tuple[int,int,int]], src: int) -> list[float]:
dist = [float('inf')] * n
dist[src] = 0
# Relax all edges n-1 times
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Detect negative-weight cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Negative weight cycle detected")
return distfunction bellmanFord(n, edges, src) {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
// Relax all edges n-1 times
for (let i = 1; i < n; i++) {
for (const [u, v, w] of edges) {
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
}
}
// Detect negative-weight cycle
for (const [u, v, w] of edges) {
if (dist[u] + w < dist[v])
throw new Error('Negative weight cycle detected');
}
return dist;
}Python — Code Walkthrough
float("inf") — no overflow risk
dist = [float("inf")] * nPython's float('inf') + any number is still inf, so the overflow guard needed in C/Java is unnecessary. The relaxation condition dist[u] + w < dist[v] handles unreachable nodes naturally.
range(n-1) for V−1 iterations
for _ in range(n - 1)The loop variable is unused, so _ is the conventional placeholder. range(n-1) generates exactly n−1 iterations — the number of relaxation passes required.
Tuple unpacking for edges
for u, v, w in edgesEach edge is a tuple (u, v, w). Python's unpacking assignment names all three components in one readable line, avoiding indexing like edge[0], edge[1], edge[2].
raise ValueError on negative cycle
raise ValueError("Negative weight cycle detected")Raising an exception stops execution and propagates the error. The caller decides whether to catch and handle it or let it propagate further up the call stack.