The challenge
Find shortest distances from a source when edges may have negative weights. Detect a negative cycle reachable from that source.
Edges are directed. A negative cycle in a disconnected, unreachable component does not invalidate this source’s distances.
Example
With B → C of weight −2: A:0, B:3, C:1, D:4, E:5, F:1. Adding D → B of weight −3 makes a reachable negative cycle.
Use the walkthrough below to inspect the input and each state change.
See Bellman–Ford, step by step
Follow the edges. Watch the state change.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
Initialize the source at zero.
Negative edges are allowed. A pass checks every directed edge in the listed order.
distance[source] = 0View input edges
A → B (4) · A → F (1) · F → B (2) · B → C (-2) · F → E (8) · C → D (3) · D → E (1)
Source: A. Adjacency entries follow this edge order.
Put it into code
Repeated relaxation works without greedily declaring any distance final.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
from math import inf
def bellman_ford(n, edges, source):
# Directed edges: (u, v, weight).
distance = [inf] * n
distance[source] = 0
for _ in range(n - 1):
changed = False
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
changed = True
if not changed:
break
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
return None # Negative cycle reachable from source.
return distance#include <optional>
#include <tuple>
#include <vector>
using ll = long long;
constexpr ll INF = (1LL << 60);
std::optional<std::vector<ll>> bellman_ford(
int n, const std::vector<std::tuple<int, int, ll>>& edges,
int source) { // Intermediate sums must fit in long long.
std::vector<ll> distance(n, INF);
distance[source] = 0;
for (int pass = 1; pass < n; ++pass) {
bool changed = false;
for (auto [u, v, weight] : edges) {
if (distance[u] != INF && distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
changed = true;
}
}
if (!changed) break;
}
for (auto [u, v, weight] : edges)
if (distance[u] != INF && distance[u] + weight < distance[v])
return std::nullopt;
return distance;
}