pgRouting - Routing on PostgreSQL

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.

Boost Graph Inside

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) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	`ANY-NUMERICAL`	-1	Weight of the edge (target, source) , When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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

pgr_johnson - pgRouting Manual (2.5)

pgr_johnson