Supported versions: latest (3.7) 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4 2.3 2.2 2.1 2.0

pgr_floydWarshall

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

可用性

  • 版本 2.2.0

    • 签名变更

    • 不再支持旧签名

  • 版本2.0.0

    • Official function.

描述

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

主要特点是:

  • 它不返回路径。

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

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

  • Boost 返回一个 V×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 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_vidend_vid 的总成本。

另请参阅

索引和表格