pgr_johnson - pgRouting Manual (3.0)

Description

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,

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.

Signatures

Summary

pgr_johnson(edges_sql)
pgr johnson(edges_sql [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Using default

pgr_johnson(edges_sql)
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example 1

For vertices \(\{1, 2, 3, 4\}\) 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)

pgr_johnson(edges_sql[, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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)

Parameters

Inner query

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:

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns set of (start_vid, end_vid, agg_cost)

See Also

• pgr_floydWarshall

• Boost Johnson algorithm implementation.

• Queries uses the Sample Data network.

Indices and tables

• Index

• Search Page