pgr_dagShortestPath
— Returns the shortest path(s) for weighted directed acyclic graphs(DAG).
In particular, the DAG shortest paths algorithm implemented by Boost.Graph.
Warning
Possible server crash
Warning
Experimental functions
Availability
Support
Shortest Path for Directed Acyclic Graph(DAG) is a graph search algorithm that solves the shortest path problem for
weighted directed acyclic graph, producing a shortest path from
a starting vertex (start_vid
) to an ending vertex (end_vid
).
This implementation can only be used with a directed graph with no cycles i.e. directed acyclic graph.
The algorithm relies on topological sorting the dag to impose a linear ordering on the vertices, and thus is more efficient for DAG’s than either the Dijkstra or Bellman-Ford algorithm.
Summary
pgr_dagShortestPath(edges_sql, from_vid, to_vid)
pgr_dagShortestPath(edges_sql, from_vid, to_vids)
pgr_dagShortestPath(edges_sql, from_vids, to_vid)
pgr_dagShortestPath(edges_sql, from_vids, to_vids)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
pgr_dagShortestPath(edges_sql, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(1\) to vertex \(6\) |
---|
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edge_table',
1, 6
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 1 | 1 | 1 | 0
2 | 2 | 2 | 4 | 1 | 1
3 | 3 | 5 | 8 | 1 | 2
4 | 4 | 6 | -1 | 0 | 3
(4 rows)
pgr_dagShortestPath(edges_sql, from_vid, to_vids)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(1\) to vertices \(\{ 5, 6\}\) |
---|
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edge_table',
1, ARRAY[5,6]
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 1 | 1 | 1 | 0
2 | 2 | 2 | 4 | 1 | 1
3 | 3 | 5 | -1 | 0 | 2
4 | 1 | 1 | 1 | 1 | 0
5 | 2 | 2 | 4 | 1 | 1
6 | 3 | 5 | 8 | 1 | 2
7 | 4 | 6 | -1 | 0 | 3
(7 rows)
pgr_dagShortestPath(edges_sql, from_vids, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertices \(\{1, 3\}\) to vertex \(6\) |
---|
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[1,3], 6
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 1 | 1 | 1 | 0
2 | 2 | 2 | 4 | 1 | 1
3 | 3 | 5 | 8 | 1 | 2
4 | 4 | 6 | -1 | 0 | 3
5 | 1 | 3 | 5 | 1 | 0
6 | 2 | 6 | -1 | 0 | 1
(6 rows)
pgr_dagShortestPath(edges_sql, from_vids, to_vids)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertices \(\{1, 4\}\) to vertices \(\{12, 6\}\) |
---|
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edge_table',
ARRAY[1, 4],ARRAY[12,6]
);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 1 | 1 | 1 | 0
2 | 2 | 2 | 4 | 1 | 1
3 | 3 | 5 | 8 | 1 | 2
4 | 4 | 6 | -1 | 0 | 3
5 | 1 | 1 | 1 | 1 | 0
6 | 2 | 2 | 4 | 1 | 1
7 | 3 | 5 | 10 | 1 | 2
8 | 4 | 10 | 12 | 1 | 3
9 | 5 | 11 | 13 | 1 | 4
10 | 6 | 12 | -1 | 0 | 5
11 | 1 | 4 | 16 | 1 | 0
12 | 2 | 9 | 15 | 1 | 1
13 | 3 | 12 | -1 | 0 | 2
(13 rows)
Description of the parameters of the signatures
Parameter | Type | Default | Description |
---|---|---|---|
edges_sql | TEXT |
SQL query as described above. | |
start_vid | BIGINT |
Identifier of the starting vertex of the path. | |
start_vids | ARRAY[BIGINT] |
Array of identifiers of starting vertices. | |
end_vid | BIGINT |
Identifier of the ending vertex of the path. | |
end_vids | ARRAY[BIGINT] |
Array of identifiers of ending vertices. |
Column | Type | Default | Description |
---|---|---|---|
id | ANY-INTEGER |
Identifier of the edge. | |
source | ANY-INTEGER |
Identifier of the first end point vertex of the edge. | |
target | ANY-INTEGER |
Identifier of the second end point vertex of the edge. | |
cost | ANY-NUMERICAL |
Weight of the edge (source, target)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Weight of the edge (target, source),
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Column | Type | Description |
---|---|---|
seq | INT |
Sequential value starting from 1. |
path_seq | INT |
Relative position in the path. Has value 1 for the beginning of a path. |
start_vid | BIGINT |
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
end_vid | BIGINT |
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
node | BIGINT |
Identifier of the node in the path from start_vid to end_vid . |
edge | BIGINT |
Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path. |
cost | FLOAT |
Cost to traverse from node using edge to the next node in the path sequence. |
agg_cost | FLOAT |
Aggregate cost from start_v to node . |
Indices and tables