pgr_dijkstra (V 2.0)- Shortest Path Dijkstra¶
Name¶
pgr_dijkstra
— Returns the shortest path using Dijkstra algorithm.
Synopsis¶
Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.
pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
boolean directed, boolean has_rcost);
Warning
This signature is being deprecated in version 2.1, Please use it
without the has_rcost
flag instead:
pgr_dijkstra(sql, source, target, directed)
Description¶
sql: | a SQL query, which should return a set of rows with the following columns: SELECT id, source, target, cost [,reverse_cost] FROM edge_table
|
||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
source: |
|
||||||||||
target: |
|
||||||||||
directed: |
|
||||||||||
has_rcost: | if |
Returns set of pgr_costResult[]:
seq: | row sequence |
---|---|
id1: | node ID |
id2: | edge ID (-1 for the last row) |
cost: | cost to traverse from id1 using id2 |
History
- Renamed in version 2.0.0
Examples: Directed¶
- Without
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2,3, true, false
);
seq | node | edge | cost
-----+------+------+------
(0 rows)
- With
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2,3, true, true
);
seq | node | edge | cost
-----+------+------+------
0 | 2 | 4 | 1
1 | 5 | 8 | 1
2 | 6 | 9 | 1
3 | 9 | 16 | 1
4 | 4 | 3 | 1
5 | 3 | -1 | 0
(6 rows)
Examples: Undirected¶
- Without
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
2, 3, false, false
);
seq | node | edge | cost
-----+------+------+------
0 | 2 | 4 | 1
1 | 5 | 8 | 1
2 | 6 | 5 | 1
3 | 3 | -1 | 0
(4 rows)
- With
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 3, false, true
);
seq | node | edge | cost
-----+------+------+------
0 | 2 | 2 | 1
1 | 3 | -1 | 0
(2 rows)
The queries use the Sample Data network.