ST_ShortestPath

Signatures

-- Input type:
--     TABLE[EDGE_ID, START_NODE, END_NODE[, w][, eo][, THE_GEOM]]
-- Return type:
--     TABLE[[THE_GEOM, ]EDGE_ID, PATH_ID, PATH_EDGE_ID,
--           SOURCE, DESTINATION, WEIGHT]
ST_ShortestPath('INPUT_EDGES', 'o[ - eo]'[, 'w'], s, d);

Description

Calculates the shortest path(s) from source vertex s to destination vertex d.

Note

A note about path numbering

Multiple shortest paths are distinguished by PATH_ID, while EDGE_ID indicates the ID in the input table.
Path numbering is not unique. We use a recursive algorithm to number shortest path edges. We start at the destination vertex and work our way back to the source vertex, each time incrementing ATH_EDGE_ID by 1. If at any point we reach the source vertex, we increment PATH_ID by 1 since we will be numbering a new shortest path. As a consequence, PATH_EDGE_ID always indicates the number of edges in this shortest path before reaching the destination vertex.

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`). If it contains a Geometry column, this column will be returned in the output table.
`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

Examples

In the following examples, we will use the geometrical data below as input.

DROP TABLE IF EXISTS INPUT;
CREATE TABLE INPUT(THE_GEOM GEOMETRY(LINESTRING),
                   ID INT AUTO_INCREMENT PRIMARY KEY,
                   WEIGHT DOUBLE,
                   EDGE_ORIENTATION INT);
INSERT INTO INPUT VALUES
    ('LINESTRING (0 1, 1 2)', DEFAULT, 10.0, 1),
    ('LINESTRING (1 2, 2 2)', DEFAULT, 1.0, -1),
    ('LINESTRING (1 2, 0.75 1, 1 0)', DEFAULT, 2.0,  1),
    ('LINESTRING (1 0, 1.25 1, 1 2)', DEFAULT, 3.0,  1),
    ('LINESTRING (0 1, 1 0)', DEFAULT, 5.0,  1),
    ('LINESTRING (1 0, 2 2)', DEFAULT, 9.0,  1),
    ('LINESTRING (1 0, 2 0)', DEFAULT, 2.0,  1),
    ('LINESTRING (2 2, 1.75 1, 2 0)', DEFAULT, 4.0,  1),
    ('LINESTRING (2 0, 2.25 1, 2 2)', DEFAULT, 6.0,  1),
    ('LINESTRING (2 0, 0 1)', DEFAULT, 7.0,  0),
    ('LINESTRING (3 0, 3 1)', DEFAULT, 1.0, 1),
    ('LINESTRING (3 1, 3 2)', DEFAULT, 2.0, 1);

We call ST_Graph on this input table in order to construct the node and edge tables. We give an illustration of the resulting graph. Note that we can call this function on any table containing integer columns EDGE_ID, START_NODE and END_NODE.

DROP TABLE IF EXISTS INPUT_NODES;
DROP TABLE IF EXISTS INPUT_EDGES;
CALL ST_Graph('INPUT');
SELECT * FROM INPUT_EDGES;

EDGE_ID	START_NODE	END_NODE
1	1	2
2	2	4
3	2	3
4	3	2
5	1	3
6	3	4
7	3	5
8	4	5
9	5	4
10	5	1
11	6	7
12	7	8

Undirected unweighted

We have just enough information to consider an unweighted undirected graph. Notice there are four shortest paths from vertex 1 to vertex 4. You may have a different numbering when you execute this request.

SELECT * FROM ST_ShortestPath('INPUT_EDGES', 'undirected', 1, 4);

EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
6	1	1	3	4	1.0
5	1	2	1	3	1.0
9	2	1	5	4	1.0
10	2	2	1	5	1.0
8	3	1	5	4	1.0
10	3	2	1	5	1.0
2	4	1	2	4	1.0
1	4	2	1	2	1.0

Directed Weighted

If we want to take edge orientations and weights into account, we have to recover that information from the original input table. Notice that edge 2 is reversed and edge 10 is bidirectional (represented by edges 10 and -10 in opposite directions).

DROP TABLE IF EXISTS EDGES_EO_W;
CREATE TABLE EDGES_EO_W(EDGE_ID INT PRIMARY KEY,
                        START_NODE INT,
                        END_NODE INT,
                        WEIGHT DOUBLE,
                        EDGE_ORIENTATION INT) AS
    SELECT B.EDGE_ID,
           B.START_NODE,
           B.END_NODE,
           A.WEIGHT,
           A.EDGE_ORIENTATION
    FROM INPUT A, INPUT_EDGES B
    WHERE A.ID=B.EDGE_ID;
SELECT * FROM EDGES_EO_W;

EDGE_ID	START_NODE	END_NODE	WEIGHT	EDGE_ORIENTATION
1	1	2	10.0	1
2	2	4	1.0	-1
3	2	3	2.0	1
4	3	2	3.0	1
5	1	3	5.0	1
6	3	4	9.0	1
7	3	5	2.0	1
8	4	5	4.0	1
9	5	4	6.0	1
10	5	1	7.0	0
11	6	7	1.0	1
12	7	8	2.0	1

Now we may consider a directed weighted graph. Again, notice this is not really a “tree” in the mathematical sense since there are two shortest paths from vertex 1 to vertex 5. We illustrate the two possible numberings of these paths.

SELECT * FROM ST_ShortestPath('EDGES_EO_W',
        'directed - EDGE_ORIENTATION', 'WEIGHT', 1, 4);

Numbering 1:

EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
9	1	1	5	4	6.0
7	1	2	3	5	2.0
5	1	3	1	3	5.0
-10	2	2	1	5	7.0

Numbering 2:

EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
9	1	1	5	4	6.0
-10	1	2	1	5	7.0
7	2	2	3	5	2.0
5	2	3	1	3	5.0

Unreachable vertices

If the destination vertex is unreachable from the source vertex, a table with a single line is returned:

SELECT * FROM ST_ShortestPath('INPUT_EDGES', 'undirected', 1, 6);

EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
-1	-1	-1	1	6	Infinity

Including Geometries

To include Geometries in the result, there are two methods.

METHOD 1: Include Geometries in the input table.

DROP TABLE IF EXISTS EDGES_EO_W_GEOM;
CREATE TABLE EDGES_EO_W_GEOM(EDGE_ID INT PRIMARY KEY,
                             START_NODE INT,
                             END_NODE INT,
                             EDGE_ORIENTATION INT,
                             WEIGHT DOUBLE,
                             THE_GEOM GEOMETRY) AS
    SELECT B.EDGE_ID,
           B.START_NODE,
           B.END_NODE,
           A.EDGE_ORIENTATION,
           A.WEIGHT,
           A.THE_GEOM
    FROM INPUT A, INPUT_EDGES B
    WHERE A.ID=B.EDGE_ID;

The input table’s Geometries are automatically returned in the result.

SELECT * FROM ST_ShortestPath('EDGES_EO_W_GEOM', 
        'directed - EDGE_ORIENTATION', 'weight', 1, 4);

THE_GEOM	EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
LINESTRING (2 0, 2.25 1, 2 2)	9	1	1	5	4	6.0
LINESTRING (1 0, 2 0)	7	1	2	3	5	2.0
LINESTRING (0 1, 1 0)	5	1	3	1	3	5.0
LINESTRING (2 0, 0 1)	-10	2	2	1	5	7.0

METHOD 2: Recover Geometries after calculation. Notice the call to the ABS function (edge ids could be negative). We get the same result.

SELECT A.THE_GEOM,
       B.EDGE_ID,
       B.PATH_ID,
       B.PATH_EDGE_ID,
       B.SOURCE,
       B.DESTINATION,
       B.WEIGHT
FROM INPUT A,
     (SELECT * FROM ST_ShortestPath('EDGES_EO_W_GEOM',
        'directed - EDGE_ORIENTATION', 'weight', 1, 4)) B
WHERE A.ID=ABS(B.EDGE_ID);

THE_GEOM	EDGE_ID	PATH_ID	PATH_EDGE_ID	SOURCE	DESTINATION	WEIGHT
LINESTRING (2 0, 2.25 1, 2 2)	9	1	1	5	4	6.0
LINESTRING (1 0, 2 0)	7	1	2	3	5	2.0
LINESTRING (0 1, 1 0)	5	1	3	1	3	5.0
LINESTRING (2 0, 0 1)	-10	2	2	1	5	7.0

Exercises

Check that the sum of the weights of the edges in the path returned by ST_ShortestPath is equal to the path length returned by ST_ShortestPathLength. Watch out for multiple shortest paths!