ST_ShortestPathLength
Signatures
-- Input type:
-- TABLE[EDGE_ID, START_NODE, END_NODE[, w][, eo]]
-- Return type:
-- TABLE[SOURCE, DESTINATION, DISTANCE]
ST_ShortestPathLength('INPUT_EDGES', 'o[ - eo]'[, 'w'],
s, d); -- One-to-One
ST_ShortestPathLength('INPUT_EDGES', 'o[ - eo]'[, 'w'],
s, 'ds'); -- One-to-Several
ST_ShortestPathLength('INPUT_EDGES', 'o[ - eo]'[, 'w'],
s); -- One-to-All
ST_ShortestPathLength('INPUT_EDGES', 'o[ - eo]'[, 'w'],
'SDT'); -- Many-to-ManyDescription
Calculates the length(s) of shortest path(s) among vertices in a graph. Can be used to calculate distance matrices.
Input parameters
| Variable | Meaning |
|---|---|
INPUT_EDGES |
Table containing integer columns EDGE_ID, START_NODE and END_NODE; and optionally a weight column w (if the graph is weighted) and/or an edge orientation column eo (required if global orientation is not undirected) |
o |
Global orientation string: directed, reversed or undirected |
eo |
Edge orientation column name indicating individual edge orientations: 1 (directed), -1 (reversed) or 0 (undirected); required if global orientation is directed or reversed |
w |
Edge weights column name |
s |
Source vertex id |
d |
Destination vertex id |
ds |
Comma-separated destination string: 'dest1, dest2, ...' |
SDT |
Source-Destination table name; must contain columns SOURCE and DESTINATION containing integer vertex ids |
Examples
-- Prepare example data. We give an illustration of the graph this
-- represents below. In order to visualize how these distances are
-- calculated, please see the documentation of ST_ShortestPath and
-- ST_ShortestPathTree.
CREATE TABLE EDGES(EDGE_ID INT AUTO_INCREMENT PRIMARY KEY,
START_NODE INT,
END_NODE INT,
WEIGHT DOUBLE,
EDGE_ORIENTATION INT);
INSERT INTO EDGES VALUES
(DEFAULT, 1, 2, 10.0, 1),
(DEFAULT, 2, 4, 1.0, -1),
(DEFAULT, 2, 3, 2.0, 1),
(DEFAULT, 3, 2, 3.0, 1),
(DEFAULT, 1, 3, 5.0, 1),
(DEFAULT, 3, 4, 9.0, 1),
(DEFAULT, 3, 5, 2.0, 1),
(DEFAULT, 4, 5, 4.0, 1),
(DEFAULT, 5, 4, 6.0, 1),
(DEFAULT, 5, 1, 7.0, 0),
(DEFAULT, 6, 7, 1.0, 1),
(DEFAULT, 7, 8, 2.0, 1);
One-to-One
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1, 5);
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 5 | 7.0 |
-- We can obtain just the distance if we want:
SELECT DISTANCE FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1, 5);
-- | DISTANCE |
-- |----------|
-- | 7.0 |
-- In an unweighted graph, d(1, 5) is just the number of steps from
-- vertex 1 to vertex 5. They are connected by edge -10.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
1, 5);
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 5 | 1.0 |
-- The distance function is not necessarily symmetric in directed
-- graphs: d(a, b) != d(b, a)
SELECT (SELECT DISTANCE FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1, 3)) DIST_1_3,
(SELECT DISTANCE FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 3, 1)) DIST_3_1;
-- | DIST_1_3 | DIST_3_1 |
-- |----------|----------|
-- | 5.0 | 9.0 |
-- However, it is symmetric in undirected graphs:
SELECT (SELECT DISTANCE FROM
ST_ShortestPathLength('EDGES',
'undirected',
'WEIGHT', 1, 3)) DIST_1_3,
(SELECT DISTANCE FROM
ST_ShortestPathLength('EDGES',
'undirected',
'WEIGHT', 3, 1)) DIST_3_1;
-- | DIST_1_3 | DIST_3_1 |
-- |----------|----------|
-- | 5.0 | 5.0 |
-- Vertex 6 is not reachable from vertex 1.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1, 6);
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 6 | Infinity |One-to-Several
-- Here we calculate d(1, 3), d(1, 5) and d(1, 6) in a single
-- request. Since vertex 6 is not reachable from vertex 1, it is not
-- returned in the list.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1, '3, 5, 6');
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 3 | 5.0 |
-- | 1 | 5 | 7.0 |One-to-All
-- Here we calculate d(1, *), i.e., the distance from vertex 1 to
-- all reachable vertices. Notice that vertices 6, 7 and 8 are not
-- reachable from vertex 1, so they do not show up in the list.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 1);
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 4 | 13.0 |
-- | 1 | 3 | 5.0 |
-- | 1 | 2 | 8.0 |
-- | 1 | 5 | 7.0 |
-- | 1 | 1 | 0.0 |
-- The only vertices reachable from vertex 6 are vertices 6, 7 and
-- 8.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 6);
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 6 | 7 | 1.0 |
-- | 6 | 8 | 3.0 |
-- | 6 | 6 | 0.0 |Many-to-Many (distance matrices)
-- Create a source-destination table:
CREATE TABLE SDT(SOURCE INT,
DESTINATION INT) AS
SELECT A.X, B.X
FROM SYSTEM_RANGE(1, 8) A,
SYSTEM_RANGE(1, 8) B;
-- Only vertices reachable from each source are returned.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'directed - EDGE_ORIENTATION',
'WEIGHT', 'SDT')
ORDER BY SOURCE, DESTINATION ASC;
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 1 | 0.0 |
-- | 1 | 2 | 8.0 |
-- | 1 | 3 | 5.0 |
-- | 1 | 4 | 13.0 |
-- | 1 | 5 | 7.0 |
-- | 2 | 1 | 11.0 |
-- | 2 | 2 | 0.0 |
-- | 2 | 3 | 2.0 |
-- | 2 | 4 | 10.0 |
-- | 2 | 5 | 4.0 |
-- | 3 | 1 | 9.0 |
-- | 3 | 2 | 3.0 |
-- | 3 | 3 | 0.0 |
-- | 3 | 4 | 8.0 |
-- | 3 | 5 | 2.0 |
-- | 4 | 1 | 11.0 |
-- | 4 | 2 | 1.0 |
-- | 4 | 3 | 3.0 |
-- | 4 | 4 | 0.0 |
-- | 4 | 5 | 4.0 |
-- | 5 | 1 | 7.0 |
-- | 5 | 2 | 7.0 |
-- | 5 | 3 | 9.0 |
-- | 5 | 4 | 6.0 |
-- | 5 | 5 | 0.0 |
-- | 6 | 6 | 0.0 |
-- | 6 | 7 | 1.0 |
-- | 6 | 8 | 3.0 |
-- | 7 | 7 | 0.0 |
-- | 7 | 8 | 2.0 |
-- | 8 | 8 | 0.0 |
-- The following example shows that the distance matrix D' of a graph
-- G' whose edges are obtained from a graph G by reversing the
-- orientation of every edge is the transpose of the distance matric D
-- of G: D' = D_transpose.
SELECT * FROM
ST_ShortestPathLength('EDGES',
'reversed - EDGE_ORIENTATION',
'WEIGHT', 'SDT')
ORDER BY DESTINATION, SOURCE ASC;
-- | SOURCE | DESTINATION | DISTANCE |
-- |--------|-------------|----------|
-- | 1 | 1 | 0.0 |
-- | 2 | 1 | 8.0 |
-- | 3 | 1 | 5.0 |
-- | 4 | 1 | 13.0 |
-- | 5 | 1 | 7.0 |
-- | 1 | 2 | 11.0 |
-- | 2 | 2 | 0.0 |
-- | 3 | 2 | 2.0 |
-- | 4 | 2 | 10.0 |
-- | 5 | 2 | 4.0 |
-- | 1 | 3 | 9.0 |
-- | 2 | 3 | 3.0 |
-- | 3 | 3 | 0.0 |
-- | 4 | 3 | 8.0 |
-- | 5 | 3 | 2.0 |
-- | 1 | 4 | 11.0 |
-- | 2 | 4 | 1.0 |
-- | 3 | 4 | 3.0 |
-- | 4 | 4 | 0.0 |
-- | 5 | 4 | 4.0 |
-- | 1 | 5 | 7.0 |
-- | 2 | 5 | 7.0 |
-- | 3 | 5 | 9.0 |
-- | 4 | 5 | 6.0 |
-- | 5 | 5 | 0.0 |
-- | 6 | 6 | 0.0 |
-- | 7 | 6 | 1.0 |
-- | 8 | 6 | 3.0 |
-- | 7 | 7 | 0.0 |
-- | 8 | 7 | 2.0 |
-- | 8 | 8 | 0.0 |