SSSP

SQL function: cugraph_sssp

Official cuGraph reference: C API

Compute minimum path distances and predecessors from one source vertex, using edges.weight or unit cost 1 when that field is omitted.

Quickstart

The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight, and starts from source vertex 123. Substitute your own registered relations.

SELECT * FROM cugraph_sssp(edges => (SELECT src, dst, weight FROM target_edges), source_vertex => 123);

Inputs

Every relation is a named parenthesized SELECT subquery. The required edges role uses canonical src and dst columns; every role, its canonical columns, and their accepted Arrow types are listed under Relation arguments. Metadata validation resolves registered tables named in its JSON request.

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

Relation arguments

Argument	Required	Columns	Description
`edges`	yes	`src`, `dst`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View` `weight` (optional): `Float32`, `Float64` `edge_id` (optional): `Int32`, `Int64`	edge relation with canonical src and dst columns, plus optional weight and edge_id columns

Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.

Named value arguments

Option	Type	Default	Constraints	Description
`cutoff`	`number\|null`	`null`	min 0	optional non-negative SSSP distance cutoff
`source_vertex`	`integer\|string`	No default	required	required scalar SSSP source vertex

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; run gpu_validate_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.

SSSP has no sources relation; source_vertex takes a literal id. Look the id up by title and year first:

SELECT paper_id FROM papers
WHERE title = 'Attention is all you need' AND year = 2017;

paper_id
2963403868

The corpus stores this NeurIPS record with a lowercase title; the capitalized Attention Is All You Need is a separate arXiv record with its own id. Then build the weighted edge view and start SSSP from the resolved id:

CREATE OR REPLACE VIEW edges_time_cost AS
SELECT e.src, e.dst,
       CAST(CASE WHEN ps.year - pd.year > 1 THEN ps.year - pd.year ELSE 1 END 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 => (SELECT src, dst, weight FROM edges_time_cost),
  source_vertex => 2963403868) s  -- 'Attention is all you need' (2017)
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 CASE 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.

The clamp is spelled as CASE rather than GREATEST(1, …) because native lowering covers this CASE expression, so the joins and the weight projection run on the GPU. A GREATEST projection keeps the joins on the host, and staging all 45.6M edges there exceeds the host staging byte limit.

Limits

omitting edges.weight assigns unit cost 1 to every edge

To dry-run validate relation metadata, column types, and options without execution, see gpu_validate_call.

Quickstart​

Inputs​

Arguments and options​

Relation arguments​

Named value arguments​

Graph construction options​

Output​

Examples​

SQL-derived edge weights​

Limits​