## pgr_johnson

 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

• Version 2.2.0

• Signature change

• Old signature no longer supported

• Version 2.0.0

• Official function

Support

### 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)



#### Complete Signature

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

Example 2

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



### Parameters

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

### 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:

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

### Result Columns

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  .