pgr_johnson - pgRouting Manual (2.5)
« pgr_floydWarshall :: Contents :: pgr_bdAstar
pgr_johnson
Synopsis
pgr_johnson - Returns the sum of the costs of the shortest path for each pair of nodes in the graph using Floyd-Warshall algorithm.
Availability: 2.0.0
- Renamed on 2.2.0, previous name pgr_apspJohnson
The Johnson algorithm, is a good choice to calculate the sum of the costs of the shortest path for each pair of nodes in the graph, for sparse graphs . It usees the Boost’s implementation which runs in \(O(V E \log V)\) time,
Characteristics
- The main Characteristics are:
-
- It does not return a path.
- Returns the sum of the costs of the shortest path for each pair of nodes in the graph.
- Process is done only on edges with positive costs.
-
Boost returns a
\(V \times V\)
matrix, where the infinity values.
Represent the distance between vertices for which there is no path.
- We return only the non infinity values in form of a set of (start_vid, end_vid, agg_cost) .
- Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid) .
-
For the undirected graph, the results are symmetric.
- The agg_cost of (u, v) is the same as for (v, u) .
- When start_vid = end_vid , the agg_cost = 0.
Signature Summary
pgr_johnson(edges_sql)
pgr johnson(edges_sql, directed)
RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET
Signatures
Minimal Signature
pgr_johnson(edges_sql)
RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET
Example 1: | On a directed graph. |
---|
SELECT * FROM pgr_johnson(
'SELECT source, target, cost FROM edge_table WHERE id < 5
ORDER BY id'
);
start_vid end_vid agg_cost
-----------+---------+----------
1 2 1
1 5 2
2 5 1
(3 rows)
Complete Signature
pgr_johnson(edges_sql, directed)
RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET
Example 2: | On an undirected graph. |
---|
SELECT * FROM pgr_johnson(
'SELECT source, target, cost FROM edge_table WHERE id < 5
ORDER BY id',
false
);
start_vid end_vid agg_cost
-----------+---------+----------
1 2 1
1 5 2
2 1 1
2 5 1
5 1 2
5 2 1
(6 rows)
Description of the Signatures
Description of the edges_sql query (id is not necessary)
edges_sql: | an SQL query, which should return a set of rows with the following columns: |
---|
Column | Type | Default | Description |
---|---|---|---|
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 |
Description of the parameters of the signatures
Receives (edges_sql, directed)
Parameter | Type | Description |
---|---|---|
edges_sql | TEXT | SQL query as described above. |
directed | BOOLEAN | (optional) Default is true (is directed). When set to false the graph is considered as Undirected |
Description of the return values
Returns set of (start_vid, end_vid, agg_cost)
Column | Type | Description |
---|---|---|
start_vid | BIGINT | Identifier of the starting vertex. |
end_vid | BIGINT | Identifier of the ending vertex. |
agg_cost | FLOAT | Total cost from start_vid to end_vid . |
History
- Re-design of pgr_apspJohnson in Version 2.2.0
See Also
- pgr_floydWarshall
- Boost Johnson algorithm implementation.
- Queries uses the Sample Data network.
Indices and tables
« pgr_floydWarshall :: Contents :: pgr_bdAstar