pgr_johnson - pgRouting Manual (3.3)

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.

• Recommended, use a bounding box of no more than 3500 edges.

Signatures

Summary

Example :

For a directed subgraph with edges \(\{1, 2, 3, 4\}\) .

SELECT * FROM pgr_johnson(
  'SELECT source, target, cost FROM edges
  WHERE id < 5'
) ORDER BY start_vid, end_vid;
 start_vid  end_vid  agg_cost
-----------+---------+----------
         5        6         1
         5        7         2
         6        7         1
(3 rows)

Parameters

Inner Queries

Result Columns

Set of (start_vid, end_vid, agg_cost)

See Also

• pgr_floydWarshall

• Boost Johnson

• Queries uses the Sample Data network.

Indices and tables

• Index

• Search Page