Bellman-Ford Single-Source Shortest Paths

Single-source shortest paths that admit negative edge weights and detect negative cycles

Category: pathfinding

Syntax

SELECT * FROM graph_bellmanford(table_name, source_id)

Description

graph_bellmanford computes single-source shortest paths from a given source to every node in the graph using the Bellman-Ford relaxation method. Unlike Dijkstra, Bellman-Ford admits NEGATIVE edge weights, which arise in cost-with-discount models, currency-arbitrage detection, profit/loss network flow, and any setting where edges may represent both gains and losses. The cost of this generality is asymptotic: time complexity is O(V * E) versus Dijkstra's O(E + V log V), so on dense or large graphs with strictly non-negative weights graph_shortest_path or graph_deltastepping will be substantially faster. The CPU implementation runs up to V - 1 relaxation rounds. Each round scans every vertex, and for every outgoing edge, attempts dist[u] := min(dist[u], dist[v] + w). The loop terminates early when a round changes nothing, so the practical runtime on shallow graphs is closer to O(diameter * E) than to the worst-case O(V * E). After the relaxation loop, the implementation runs one extra round (the V-th round): if any edge can still be relaxed, a negative-weight cycle is reachable from the source, and the function raises InvalidArgument with the message "bellman_ford: negative-weight cycle reachable from source". A graph that contains a negative cycle reachable from the source is mathematically ill-posed for shortest paths (you can always go around the cycle once more to shave another unit of cost), so surfacing it as an error is the correct behaviour. GPU acceleration is wired in. The dispatch lives in delta-forge-graph-gpu/src/algorithms/bellman_ford.rs and is selected when the planner chooses the GPU executor. It keeps the per-edge relax operator and per-destination minimum-reduction pattern that cuGraph's SSSP uses, but drops the near-far bucket logic (which assumes non-negative weights) in favour of the classic up-to-V-1 host-driven relaxation rounds with early exit. The V-th round detects a reachable negative-weight cycle and surfaces it as GpuError::AlgorithmError, matching the CPU contract. The GPU dispatch also rejects non-finite weights on the host before any kernel is dispatched, because f32 NaN/INF would poison the atomic-min reduction. Output shape is one row per node, including the source (distance 0) and every unreachable node (distance = +Infinity). The schema matches graph_deltastepping exactly, so the two single-source shortest-path functions are drop-in interchangeable on the read side once you know whether your graph has negative weights.

Parameters

Name	Type	Description
`table_name`		Name of the registered edge table. Source and target columns are auto-detected (src/source/src_id, dst/target/dst_id). A weight column, if present, is used as the edge cost and may be negative; non-finite weights (NaN, +/-INF) are rejected at runtime. If the weight column is absent every edge has weight 1.0.
`source_id`		Starting node id. Must exist in the graph. If the id is out of range the function returns an empty result set; if the graph is empty the function returns an empty result set without dispatching any work.

Examples

CREATE TABLE flow AS
SELECT * FROM VALUES
  (1, 2, 4.0),
  (1, 3, 5.0),
  (2, 3, -3.0),
  (3, 4, 2.0),
  (2, 4, 6.0)
AS t(src, dst, weight);

SELECT node_id, distance
FROM graph_bellmanford('flow', 1)
ORDER BY distance;

SELECT node_id, distance
FROM graph_bellmanford('flow', 1)
WHERE distance < 'Infinity'::DOUBLE
ORDER BY distance;

-- Adding (3 -> 2, -5.0) creates a cycle 2 -> 3 -> 2 with total weight -8.
-- Invoking graph_bellmanford on a source that can reach this cycle raises
-- InvalidArgument: "bellman_ford: negative-weight cycle reachable from source".
CREATE TABLE flow_with_cycle AS
SELECT * FROM VALUES
  (1, 2, 4.0),
  (2, 3, -3.0),
  (3, 2, -5.0),
  (3, 4, 2.0)
AS t(src, dst, weight);
SELECT node_id, distance FROM graph_bellmanford('flow_with_cycle', 1);

SELECT node_id, distance
FROM graph_bellmanford('flow', 1)
WHERE distance < 'Infinity'::DOUBLE AND node_id <> 1
ORDER BY distance
LIMIT 5;

-- CPU run (default for small graphs)
SELECT node_id, distance FROM graph_bellmanford('flow', 1);
-- GPU run on hardware that has a discrete or integrated wgpu adapter
SELECT node_id, distance FROM graph_bellmanford('flow', 1) /*+ ON GPU */;

Pitfalls

A negative-weight cycle reachable from the source causes the function to raise InvalidArgument (CPU) or GpuError::AlgorithmError (GPU) rather than return a result. This is intentional: shortest paths are undefined when you can loop around a negative cycle to shave more cost. If your data may legitimately contain such cycles you must either pre-filter them out or wrap the call in error-handling logic; the function will not return partial answers.
Non-finite edge weights (NaN, +Infinity, -Infinity) are rejected at runtime. Validate or clean the weight column before invocation. The CPU implementation raises InvalidArgument the first time it inspects such an edge; the GPU dispatch rejects them on the host before launching any kernel.
Asymptotic cost is O(V * E). On a 10 million edge graph with a few thousand nodes Bellman-Ford is roughly V times slower than Dijkstra. Prefer graph_shortest_path or graph_deltastepping when you know all weights are non-negative.
Edge direction is respected. Bellman-Ford is a single-source algorithm on the directed forward graph; if you want the equivalent on an undirected graph, insert both (a, b) and (b, a) rows in the source table.
The result includes every node, including unreachable ones with distance = +Infinity. Add WHERE distance < 'Infinity'::DOUBLE if your downstream pipeline cannot tolerate infinite values.
Unlike graph_shortest_path, Bellman-Ford does not stop early when one specific target is found. It computes distances to every node from the source. If you only need one source-target pair on a graph with non-negative weights, graph_shortest_path is strictly preferable.