Fork me on GitHub

# ST_ShortestPath

### Description

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

##### 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 `PATH_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

##### Exercises
1. 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!