Bellman–Ford¶
Use Bellman–Ford for single-source shortest paths when directed edges may have negative weight and reachable negative cycles must be detected.
Why Dijkstra is invalid¶
Dijkstra finalizes the next smallest tentative distance. A later negative edge can improve a vertex that appeared final, breaking that proof. Bellman–Ford does not finalize vertices early; it repeatedly relaxes every edge.
State and invariant¶
distance[v] is the best length found from the source to v.
After pass i, every shortest path using at most i edges has been accounted
for. Any simple shortest path contains at most V - 1 edges, so V - 1
passes are enough when no reachable negative cycle exists.
flowchart LR
accTitle: Bellman-Ford relaxation and negative-cycle flow
accDescr: Initialize the source, relax every reachable edge for at most V minus one passes, stop at a fixed point, then use one extra pass to detect a reachable negative cycle.
subgraph S["Build distances"]
direction TB
A["Initialize<br/>source 0 · others infinity"] --> B["Relax every reachable edge<br/>for one full pass"]
B --> C["Repeat until unchanged<br/>or V-1 passes total"]
end
subgraph V["Explain why iteration stopped"]
direction TB
D{"Fixed point reached early?"} -->|"yes"| E["Distances are final"]
D -->|"no, pass limit reached"| F["Scan every edge<br/>one extra time"]
end
subgraph P["Proof check"]
direction TB
G{"Reachable improvement?"} -->|"yes"| H["Negative cycle"]
G -->|"no"| I["Distances are final"]
end
C --> D
F --> GRead each full edge scan as one DP layer: it permits shortest paths with one more edge. The final scan is a proof check, not another distance-building pass.
Annotated blueprint¶
distance[*] = infinity
distance[source] = 0
repeat V - 1 times:
changed = false
for each directed edge (u, v, weight):
if distance[u] is infinity: continue # edge is unreachable
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight # relax one more edge
changed = true
if not changed: break # fixed point reached early
for each edge (u, v, weight):
if reachable u can still improve v:
report a reachable negative cycle
The reachability guard matters: a negative cycle in a disconnected component does not invalidate distances from this source.
Worked signal¶
Currency exchange can use -log(rate) as an edge weight. A negative cycle then
represents a product of exchange rates greater than one—an arbitrage cycle.
Complexity and traps¶
- Time:
O(VE). - Extra space:
O(V)without path reconstruction. - Use a safe infinity sentinel and guard before addition.
- Decide whether to return a negative-cycle flag, raise an error, or recover the cycle.
- Do not confuse “negative edge exists” with “reachable negative cycle exists.”
Reference¶
Tested template¶
def bellman_ford(
vertex_count: int, edges: Sequence[tuple[int, int, int]], source: int
) -> list[float | int]:
"""Return shortest distances, rejecting a reachable negative cycle."""
_validate_vertex(source, vertex_count, "source")
for left, right, _weight in edges:
_validate_vertex(left, vertex_count, "edge endpoint")
_validate_vertex(right, vertex_count, "edge endpoint")
distance: list[float | int] = [inf] * vertex_count
distance[source] = 0
for _ in range(vertex_count - 1):
changed = False
for left, right, weight in edges:
if distance[left] != inf and distance[left] + weight < distance[right]:
# Relax only from a vertex the source can reach.
distance[right] = distance[left] + weight
changed = True
if not changed:
break
for left, right, weight in edges:
if distance[left] != inf and distance[left] + weight < distance[right]:
raise ValueError("reachable negative cycle")
return distance
inline std::vector<long long> bellman_ford(
int vertex_count,
const std::vector<std::tuple<int, int, long long>>& edges, int source) {
if (vertex_count <= 0) {
throw std::invalid_argument("vertex_count must be positive");
}
validate_vertex(source, static_cast<std::size_t>(vertex_count), "source");
for (const auto& edge : edges) {
validate_vertex(std::get<0>(edge), vertex_count, "edge endpoint");
validate_vertex(std::get<1>(edge), vertex_count, "edge endpoint");
}
const long long infinity = std::numeric_limits<long long>::max();
std::vector<long long> distance(vertex_count, infinity);
distance[source] = 0;
for (int pass = 0; pass < vertex_count - 1; ++pass) {
bool changed = false;
for (const auto& edge : edges) {
const int left = std::get<0>(edge);
const int right = std::get<1>(edge);
const long long weight = std::get<2>(edge);
if (distance[left] == infinity) {
continue;
}
if ((weight > 0 && distance[left] > infinity - weight) ||
(weight < 0 &&
distance[left] < std::numeric_limits<long long>::min() - weight)) {
throw std::overflow_error("Bellman-Ford distance overflow");
}
const long long candidate = distance[left] + weight;
if (candidate < distance[right]) {
// Relax only from a vertex the source can reach.
distance[right] = candidate;
changed = true;
}
}
if (!changed) {
break;
}
}
for (const auto& edge : edges) {
const int left = std::get<0>(edge);
const int right = std::get<1>(edge);
const long long weight = std::get<2>(edge);
if (distance[left] == infinity) {
continue;
}
if ((weight > 0 && distance[left] > infinity - weight) ||
(weight < 0 &&
distance[left] < std::numeric_limits<long long>::min() - weight)) {
throw std::overflow_error("Bellman-Ford distance overflow");
}
if (distance[left] + weight < distance[right]) {
throw std::invalid_argument("reachable negative cycle");
}
}
return distance;
}
inline std::vector<long long> bellman_ford(
int vertex_count,
const std::vector<std::tuple<int, int, long long>>& edges, int source) {
if (vertex_count <= 0) {
throw std::invalid_argument("vertex_count must be positive");
}
validate_vertex(source, static_cast<std::size_t>(vertex_count), "source");
for (const auto& edge : edges) {
validate_vertex(std::get<0>(edge), vertex_count, "edge endpoint");
validate_vertex(std::get<1>(edge), vertex_count, "edge endpoint");
}
const long long infinity = std::numeric_limits<long long>::max();
std::vector<long long> distance(vertex_count, infinity);
distance[source] = 0;
for (int pass = 0; pass < vertex_count - 1; ++pass) {
bool changed = false;
for (const auto& edge : edges) {
const int left = std::get<0>(edge);
const int right = std::get<1>(edge);
const long long weight = std::get<2>(edge);
if (distance[left] == infinity) {
continue;
}
if ((weight > 0 && distance[left] > infinity - weight) ||
(weight < 0 &&
distance[left] < std::numeric_limits<long long>::min() - weight)) {
throw std::overflow_error("Bellman-Ford distance overflow");
}
const long long candidate = distance[left] + weight;
if (candidate < distance[right]) {
// Relax only from a vertex the source can reach.
distance[right] = candidate;
changed = true;
}
}
if (!changed) {
break;
}
}
for (const auto& edge : edges) {
const int left = std::get<0>(edge);
const int right = std::get<1>(edge);
const long long weight = std::get<2>(edge);
if (distance[left] == infinity) {
continue;
}
if ((weight > 0 && distance[left] > infinity - weight) ||
(weight < 0 &&
distance[left] < std::numeric_limits<long long>::min() - weight)) {
throw std::overflow_error("Bellman-Ford distance overflow");
}
if (distance[left] + weight < distance[right]) {
throw std::invalid_argument("reachable negative cycle");
}
}
return distance;
}
The tested contract raises only for a negative cycle reachable from source;
an unreachable negative cycle cannot affect those distances.