pgr_floydWarshall - pgRouting Manual (3.2)

Description

The Floyd-Warshall algorithm, also known as Floyd’s 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 dense graphs . We use Boost’s implementation which runs in \(\Theta(V^3)\) 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

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

Using defaults

pgr_floydWarshall(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_floydWarshall(
    'SELECT id, source, target, cost FROM edge_table where id < 5'
);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         1        2         1
         1        5         2
         2        5         1
(3 rows)

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

SELECT * FROM pgr_floydWarshall(
    'SELECT id, source, target, cost FROM edge_table where id < 5',
    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_johnson

• Boost floyd-Warshall algorithm

• Queries uses the Sample Data network.

Indices and tables

• Index

• Search Page