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-Many

Description

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