pgr_apspJohnson - All Pairs Shortest Path, Johnson’s Algorithm¶
Name¶
pgr_apspJohnson - Returns all costs for each pair of nodes in the graph.
Synopsis¶
Johnson’s algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge weighted, directed graph. Returns a set of pgr_costResult (seq, id1, id2, cost) rows for every pair of nodes in the graph.
pgr_costResult[] pgr_apspJohnson(sql text);
Description¶
| sql: | a SQL query that should return the edges for the graph that will be analyzed: SELECT source, target, cost FROM edge_table;
|
|---|
Returns set of pgr_costResult[]:
| seq: | row sequence |
|---|---|
| id1: | source node ID |
| id2: | target node ID |
| cost: | cost to traverse from id1 to id2 |
History
- New in version 2.0.0
Examples¶
SELECT seq, id1 AS from, id2 AS to, cost
FROM pgr_apspJohnson(
'SELECT source, target, cost FROM edge_table'
);
seq | from | to | cost
-----+------+----+------
0 | 1 | 1 | 0
1 | 1 | 2 | 1
2 | 1 | 5 | 2
3 | 1 | 6 | 3
[...]
The query uses the Sample Data network.