A* Shortest Path

Heuristic-guided single-target shortest path search between two nodes

Category: pathfinding

Syntax

SELECT * FROM graph_astar(table_name, source_id, target_id)

Description

graph_astar runs the classic A* best-first search between a single source and a single target. The search maintains a binary heap keyed by f(v) = g(v) + h(v), where g(v) is the best known cost from the source and h(v) is an admissible estimate of the remaining cost to the target. When h(v) is identically zero, A* is mathematically equivalent to Dijkstra; when h(v) is admissible and tight, A* explores far fewer nodes than Dijkstra because the heap prefers candidates that are geometrically closer to the target. The SQL table function exposes only the table name, source, and target. The current binding uses h(v) = 0 internally because the engine has no parameter surface for handing a coordinate column or a custom heuristic into the CPU search. In practice this means graph_astar today returns the same path as graph_shortest_path but in a different output shape: a (step, node_id) sequence rather than (node_id, distance, hop_count). If you have node coordinates and want a faster heuristic-guided search, expose them through Cypher MATCH ... shortestPath(...) where the planner can bind the property accessor; the underlying CPU engine in delta-forge-graph already accepts a Fn(usize) -> f64 heuristic via its public a_star entry point. A GPU shader for A* exists in delta-forge-graph-gpu (see astar.rs and astar.wgsl) and follows cuGraph's near-far pile pattern with f = g + h as the bucketing key. It is used as an internal building block by the GPU shortest_path dispatch. GPU acceleration is not wired through the graph_astar SQL table function, so an ON GPU hint on a SQL query that uses it is silently ignored and it runs on the CPU: the priority queue equivalent on the GPU still requires the same heuristic input, which the SQL surface does not yet carry. The Cypher CALL surface (USE ... ON GPU ... CALL algo.astar) does expose a GPU dispatch, returning the same step and node_id columns as the CPU path. Correctness rules enforced by the implementation: empty graph or source/target out of range yields an empty result; same-source same-target yields a single row at step 0; any edge weight that is negative or non-finite (NaN, +/-INF) raises an InvalidArgument error before the heap loop runs. Ties between equal-cost paths are resolved by first-pop-wins from the heap.

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; otherwise every edge has weight 1.0. Edge weights must be finite and non-negative or the search is rejected at runtime.
`source_id`		Starting node id. Must exist in the graph; if it does not, the function returns an empty result set rather than raising an error.
`target_id`		Destination node id. Must exist in the graph. If no directed path connects source to target, the function returns an empty result set; the function does not distinguish missing target from unreachable target.

Examples

CREATE TABLE roads AS
SELECT * FROM VALUES
  (1, 2, 4.0),
  (1, 3, 2.0),
  (2, 4, 5.0),
  (3, 2, 1.0),
  (3, 4, 8.0),
  (4, 5, 3.0)
AS t(src, dst, weight);

CREATE TABLE road_nodes AS
SELECT * FROM VALUES
  (1, 0.0, 0.0),
  (2, 1.0, 1.0),
  (3, 1.0, 0.0),
  (4, 2.0, 1.0),
  (5, 3.0, 2.0)
AS t(node_id, x, y);

SELECT step, node_id
FROM graph_astar('roads', 1, 5)
ORDER BY step;

SELECT MAX(step) AS hops FROM graph_astar('roads', 1, 5);

SELECT a.node_id AS from_node, b.node_id AS to_node
FROM graph_astar('roads', 1, 5) a
JOIN graph_astar('roads', 1, 5) b ON b.step = a.step + 1
ORDER BY a.step;

SELECT p.step, p.node_id, n.x, n.y
FROM graph_astar('roads', 1, 5) p
JOIN road_nodes n ON n.node_id = p.node_id
ORDER BY p.step;

Pitfalls

The SQL surface does not accept a heuristic or a coordinate column. graph_astar therefore runs with h(v) = 0 and behaves exactly like Dijkstra in cost, only with an output shape of (step, node_id) instead of (node_id, distance, hop_count). If you wanted the speedup that a geometric heuristic gives, this binding does not provide it. Use graph_shortest_path when you only need the path; use Cypher shortestPath when you have coordinates and want heuristic guidance.
Negative or non-finite edge weights are rejected. The CPU search raises InvalidArgument the first time it inspects such an edge, even if that edge is not on the optimal path. Validate the weight column before invoking graph_astar; route negative-weight graphs through graph_bellmanford instead.
An empty result set conflates four distinct cases: source does not exist, target does not exist, no directed path connects them, or the graph is empty. The function does not distinguish these. Check node existence separately (for example with a SELECT COUNT(*) FROM edges WHERE src = :source) if the distinction matters to the caller.
Edge direction is respected. To search an undirected graph, materialise both (a, b) and (b, a) rows in the source table; otherwise A* may report no path when one exists in the undirected sense.
The output is a node sequence, not an edge list. Reconstructing edges requires pairing consecutive rows by step; the function does not emit a row for the synthetic predecessor of the source.
GPU acceleration is not wired through the graph_astar table function, so an ON GPU hint on a SQL query that uses it is silently ignored and computation runs on the CPU priority queue. The Cypher CALL surface (USE ... ON GPU ... CALL algo.astar) does expose a GPU dispatch, returning the same step and node_id columns as the CPU path.