pgr_floydWarshall - pgRouting Manual (3.3)

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

Example :

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

SELECT * FROM pgr_floydWarshall(
  'SELECT id, source, target, cost, reverse_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        5         1
         6        7         1
         7        5         2
         7        6         1
        10        5         2
        10        6         1
        10        7         2
        15        5         3
        15        6         2
        15        7         3
        15       10         1
(13 rows)

Parameters

Inner Queries

Result Columns

Set of (start_vid, end_vid, agg_cost)

See Also

• pgr_johnson

• Boost floyd-Warshall

• Queries uses the Sample Data network.

Indices and tables

• Index

• Search Page