Shortest Path

Find the shortest weighted path between two nodes

Category: pathfinding

Syntax

SELECT * FROM graph_shortest_path(table_name, source_id, target_id [, max_length])

Description

The shortest path function finds the minimum-weight path between two specified nodes in a graph using Dijkstra's algorithm. It returns the complete sequence of nodes along the path, with cumulative distances and hop counts at each step. This is the standard approach for route planning, network latency estimation, supply chain optimization, and any scenario where the goal is to minimize the total cost of traversal between two specific points. The function loads edge data from a registered Delta table into a Compressed Sparse Row (CSR) representation. The algorithm uses a priority-queue-based Dijkstra search from the source node, terminating early when the target is reached. If a weight column is present in the table, those values determine edge costs; otherwise, all edges have unit weight (equivalent to BFS). Column names for source, target, and weight are auto-detected. If either the source or target node ID does not exist in the graph, or if no path connects them, an empty result set is returned. The time complexity is O(E + V log V) with a binary heap priority queue, where V is the vertex count and E is the edge count. The early termination when the target is found means that in practice the algorithm often explores only a fraction of the full graph. GPU acceleration is not currently available for single-pair shortest path queries. All computation runs on the CPU. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology, so repeated shortest-path queries on the same table with different source/target pairs reuse the cached graph.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table containing edge data. The table must include source and target columns (auto-detected as src/source/src_id and dst/target/dst_id). If a weight column is present, it is used for distance computation; otherwise, all edges are treated as having weight 1.0.
`source_id`		Specify the starting node ID for the path search. This must be a valid node ID present in the edge table. If the node does not exist, an empty result set is returned.
`target_id`		Specify the destination node ID for the path search. This must be a valid node ID present in the edge table. If no path exists between source and target, an empty result set is returned.
`max_length`		Maximum path length

Examples

CREATE TABLE roads AS
SELECT * FROM VALUES
  (1, 2, 7.0),
  (1, 3, 9.0),
  (1, 6, 14.0),
  (2, 3, 10.0),
  (2, 4, 15.0),
  (3, 4, 11.0),
  (3, 6, 2.0),
  (4, 5, 6.0),
  (5, 6, 9.0)
AS t(src, dst, weight);

SELECT * FROM graph_shortest_path('roads', 1, 5);

SELECT MAX(distance) AS total_distance
FROM graph_shortest_path('roads', 1, 5);

SELECT * FROM graph_shortest_path('roads', 1, 4);

SELECT p.hop_count, p.node_id, c.city_name, p.distance
FROM graph_shortest_path('roads', 1, 5) p
JOIN cities c ON p.node_id = c.id
ORDER BY p.hop_count;

SELECT 'Route A' AS route, MAX(distance) AS cost, MAX(hop_count) AS hops
FROM graph_shortest_path('roads', 1, 5)
UNION ALL
SELECT 'Route B', MAX(distance), MAX(hop_count)
FROM graph_shortest_path('roads', 1, 4);

Pitfalls

Dijkstra requires non-negative edge weights. Negative weights produce undefined behaviour (may return sub-optimal paths or fail to terminate correctly). Validate the weight column before invocation; use a different algorithm for graphs with legitimate negative weights.
The result set is the path nodes in order, not the edges. Rows represent cumulative state at each hop; there is no row for the source's parent. Clients reconstructing edge lists must pair consecutive rows by hop_count.
An empty result set means one of three things: the source does not exist, the target does not exist, or no path connects them. The function does not distinguish these cases; check node existence separately if the distinction matters.
max_length caps the path in hops, not in cumulative weight. A weighted graph where the shortest path has 5 hops but large per-edge weights will still terminate at hop 5. Use a WHERE distance <= X filter on the result if weight-based truncation is required.
Edge direction is respected. An undirected problem must be represented by inserting both (a, b) and (b, a) rows in the source table; otherwise the search may report no path when one exists in the undirected sense.
GPU acceleration is not available. Single-pair shortest-path queries run CPU-only, and the ON GPU execution hint is silently ignored.