pgr_apspWarshall - All Pairs Shortest Path, Floyd-Warshall Algorithm¶
Name¶
pgr_apspWarshall
- Returns all costs for each pair of nodes in the graph.
Synopsis¶
The Floyd-Warshall algorithm (also known as Floyd’s algorithm and other names) is a graph analysis algorithm for finding the shortest paths between all pairs of nodes in a weighted graph. Returns a set of pgr_costResult (seq, id1, id2, cost) rows for every pair of nodes in the graph.
pgr_costResult[] pgr_apspWarshall(sql text, directed boolean, reverse_cost boolean);
Description¶
sql: | a SQL query that should return the edges for the graph that will be analyzed: SELECT id, source, target, cost FROM edge_table;
|
||||||||
---|---|---|---|---|---|---|---|---|---|
directed: |
|
||||||||
reverse_cost: | if |
Returns set of pgr_costResult[]:
seq: | row sequence |
---|---|
id1: | source node ID |
id2: | target node ID |
cost: | cost to traverse from id1 to id2 |
History
- New in version 2.0.0
Examples¶
SELECT seq, id1 AS from, id2 AS to, cost
FROM pgr_apspWarshall(
'SELECT id, source, target, cost FROM edge_table',
false, false
);
seq | from | to | cost
-----+------+----+------
0 | 1 | 1 | 0
1 | 1 | 2 | 1
2 | 1 | 3 | 0
3 | 1 | 4 | -1
[...]
The query uses the Sample Data network.