SSSP

SQL function: cugraph_sssp

Official cuGraph reference: C API

Compute minimum path distances and predecessors from one source vertex, using bound edge weights or unit cost 1 when weight_col is omitted.

Signature

cugraph_sssp(table_name, source_vertex [, src_col, dst_col [, weight_col [, options_json]]])

Quickstart

The call below expects a registered edge table or view target_edges with endpoint columns src and dst, and starts from source vertex 123. Substitute your own registered relations.

SELECT * FROM cugraph_sssp('target_edges', 123);

Inputs

table_name must be a registered edge table or view (the edges role); parenthesized subqueries are not accepted, and metadata validation resolves the same registered name.

Endpoint columns accept numeric Int32, Int64 vertex IDs or logical string Utf8, LargeUtf8, Utf8View vertex IDs; string vertex-identity outputs are canonicalized to Utf8 (native mapping Int64) while scores, distances, counts, coordinates, and opaque labels stay numeric. The shared vertex-ID contract is summarized in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.

Logical string side-input limitations:

• edge ID columns and edge-ID predicate side inputs are not supported for logical string graphs

Arguments and options

Positional scalar arguments

src_col and dst_col name the edge endpoint columns; both are optional and default to src and dst.

Argument	Type	Required	Default	Notes
source_vertex	Int64|Utf8	yes
weight_col	Utf8|null	no		optional edge weight column for graph construction when supported by the algorithm; semantic effect: edge weights affect algorithm results when provided

JSON options

Option	Type	Default	Constraints	Description
cutoff	Float64|null	null	min 0	Maximum edge-weight sum to explore from the source; vertices farther than the cutoff are reported unreachable. Null means no cutoff.

Graph construction options

Graph construction follows the shared defaults (directed=true, renumbering, python_cugraph policy) documented in Graph Construction Options.

Output

Column	Type	Nullable	Description
vertex	Int64|Utf8	no	Vertex reached by the shortest-path traversal.
distance	Float64	no	Shortest weighted-path distance from the source vertex.
predecessor	Int64|Utf8	yes	Previous vertex on the shortest-path tree, null for the source or unreachable vertices.

These are generic descriptor schemas; validate the call to get the concrete, table-specific output schema.

Examples

This example runs on the citation network demo dataset.

SQL-derived edge weights

The citation edges carry a constant weight, but the weight column handed to SSSP can be computed by SQL. Joining papers on both endpoints prices each citation hop at the number of years it spans, so SSSP distance becomes the cumulative year span along the cheapest reference chain:

CREATE VIEW edges_time_cost AS
SELECT e.src, e.dst,
       CAST(GREATEST(1, ps.year - pd.year) AS DOUBLE) AS weight
FROM citation_edges e
JOIN papers ps ON ps.paper_id = e.src
JOIN papers pd ON pd.paper_id = e.dst
WHERE ps.year > 1900 AND pd.year > 1900;

SELECT CAST(ROUND(s.distance) AS BIGINT) AS time_cost, p.year, p.title
FROM cugraph_sssp('edges_time_cost', 2963403868, 'src', 'dst', 'weight') s
JOIN papers p ON p.paper_id = s.vertex
WHERE s.distance < 1e300
ORDER BY p.year ASC, s.distance ASC
LIMIT 6;

time_cost	year	title
84	1933	Algebraic Functions
82	1935	When is a Trigonometric Polynomial Not a Trigonometric Polynomial
81	1936	Correction to a Note on the Entscheidungsproblem
81	1936	Toward a Calculus of Concepts
81	1936	Set-Theoretic Foundations for Logic
81	1936	A System of Formal Logic without an Analogue to the Curry W. Operator

Starting from Attention Is All You Need (2017), the cheapest reference chains reach the 1936 foundations of computability and formal logic at a time-cost of 81 years. The GREATEST(1, …) clamp keeps weights positive (same-year and forward-dated citations cost 1), and the WHERE clause drops the handful of bogus pre-1900 years in the source data. Unreached vertices report an infinite distance, filtered here with s.distance < 1e300.

Limits

• omitting weight_col assigns unit cost 1 to every edge

Validate the call

Dry-run validation checks registered relation metadata, column presence, static dtypes, and options only; it does not scan edge data, construct a graph, or prove source-vertex existence:

SELECT * FROM gpu_validate_call(
  'cugraph_sssp',
  '{"schema_version":1,"relations":{"edges":{"table":"target_edges"}},"options":{"source_vertex":123,"src_col":"src","dst_col":"dst"}}'
);

See GPU Function Catalog API for the full gpu_validate_call contract.