pgr_floydWarshall

pgr_floydWarshall - 使用 Floyd-Warshall 算法返回图中每对节点的最短路径成本之和。

可用性

• 版本 2.2.0

  • 签名变更

  • 不再支持旧签名

• 版本2.0.0

  • Official function.

描述

Floyd-Warshall算法，也被称为 Floyd算法，是计算图中每一对节点间最短路径的路径成本总和的一种良好选择，适用于*密集图*。我们使用Boost的实现，其运行时间为： \(\Theta(V^3)\)，

主要特点是：

• 它不返回路径。

• 返回图中每对节点的最短路径成本之和。

• 仅在具有正成本的边进行处理。

• Boost 返回一个 \(V \times V\) 矩阵，其中无穷大值。 表示没有路径的顶点之间的距离。

  • 我们仅以一组 (start_vid, end_vid, agg_cost) 的形式返回非无穷大值。

• 假设返回的值存储在表中，因此唯一索引将是一对：(start_vid, end_vid)。

• 对于无向图，结果是对称的。

  • (u, v) 的 agg_cost 与 (v, u) 相同。

• 当 start_vid = end_vid 时，agg_cost = 0。

• 建议使用不超过 3500 条边的边界框。

Boost Graph Inside

签名

总结

pgr_floydWarshall(Edges SQL, [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

对于有边 \(\{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)

参数

参数	类型	默认	描述
Edges SQL	TEXT		Edges SQL 如下所述。

可选参数

列	类型	默认	描述
directed	BOOLEAN	true	当 true 时，该图被视为有 有向 如果为 false ，则该图被视为 无向。

内部查询

Edges SQL

列	类型	默认	描述
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

(start_vid, end_vid, agg_cost) 的集合

列	类型	描述
start_vid	BIGINT	起始顶点的标识符。
end_vid	BIGINT	结束顶点的标识符。
agg_cost	FLOAT	从 start_vid 到 end_vid 的总成本。

另请参阅

• pgr_johnson

• 示例数据

• Boost floyd-Warshall

索引和表格

• Index

• Search Page