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

Dijkstra - 函数族

建议

Warning

下一版本的拟议功能。

  • 它们并未正式出现在当前版本中。

  • 它们可能会正式成为下一个版本的一部分:

    • 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL

    • 名字可能不会改变。(但仍然有可能改变)

    • 签名可能不会改变。(但仍然有可能改变)

    • 功能可能不会改变。(但仍然有可能改变)

    • pgTap 测试已经完成。 但可能需要更多。

    • 文档可能需要完善。

介绍

Dijkstra算法,由荷兰计算机科学家Edsger Dijkstra于1956年提出。它是一种图搜索算法,解决具有非负边路径成本的图的最短路径问题,产生从起始顶点到结束顶点的最短路径。 该实现可以与有向图和无向图一起使用。

主要特点是:

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

    • 成本列上的负值被解释为边不存在。

  • 当存在路径时返回值。

  • 当没有路径时:

    • 当起始顶点和结束顶点相同时。

      • 未包含值 (v,v)aggregate cost0

    • 当起始顶点和结束顶点不同且不存在路径时:

      • 未包含值 (u,v)aggregate cost

  • 出于优化目的,起始顶点或结束顶点中的任何重复值都将被忽略。

  • 运行时间: O(|start vids|(VlogV+E))

Dijkstra 系列函数基于 Dijkstra 算法。

参数

类型

描述

Edges SQL

TEXT

Edges SQL 如下所述

Combinations SQL

TEXT

Combinations SQL 如下所述

start vid

BIGINT

路径起始顶点的标识符。

start vids

ARRAY[BIGINT]

起始顶点的标识符数组。

end vid

BIGINT

路径结束顶点的标识符。

end vids

ARRAY[BIGINT]

结束顶点的标识符数组。

可选参数

类型

默认

描述

directed

BOOLEAN

true

  • true 时,该图被视为有 有向

  • 如果为 false ,则该图被视为 无向

内部查询

Edges SQL

类型

默认

描述

id

ANY-INTEGER

边的标识符。

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

分量 SQL

参数

类型

描述

source

ANY-INTEGER

出发顶点的标识符。

target

ANY-INTEGER

到达顶点的标识符。

其中:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

高级文档

问题定义(高级文档)

给出以下查询:

pgr_dijkstra(sql,startvid,endvid,directed)

其中 sql={(idi,sourcei,targeti,costi,reverse_costi)}

  • source=sourcei,

  • target=targeti,

图定义如下:

有向图

加权有向图, Gd(V,E) 的定义如下:

  • 顶点集 V

    • V=sourcetargetstartvvidendvid

  • 边集 E

    • E={ {(sourcei,targeti,costi) when cost>=0}if reverse_cost=    {(sourcei,targeti,costi) when cost>=0} {(targeti,sourcei,reverse_costi) when reverse_costi>=0}if reverse_cost

无向图

加权无向图, Gu(V,E) 的定义如下:

  • 顶点集 V

    • V=sourcetargetstartvvidendvid

  • 边集 E

    • E={ {(sourcei,targeti,costi) when cost>=0} {(targeti,sourcei,costi) when cost>=0} if reverse_cost=    {(sourcei,targeti,costi) when cost>=0} {(targeti,sourcei,costi) when cost>=0} {(targeti,sourcei,reverse_costi) when reverse_costi>=0)} {(sourcei,targeti,reverse_costi) when reverse_costi>=0)} if reverse_cost

问题

给定:

  • startvidV a starting vertex

  • endvidV an ending vertex

  • G(V,E)={Gd(V,E) if6 directed=trueGu(V,E) if5 directed=false

然后:

  • π={(path_seqi,nodei,edgei,costi,agg_costi)}

其中:
  • path_seqi=i

  • path_seq|π|=|π|

  • nodeiV

  • node1=startvid

  • node|π|=endvid

  • i|π|,(nodei,nodei+1,costi)E

  • edgei={id(nodei,nodei+1,costi)when i|π|1when i=|π|

  • costi=cost(nodei,nodei+1)

  • agg_costi={0when i=1k=1icost(nodek1,nodek)when i1

换句话说:如果 startvidendvid 之间存在最短路径,算法会根据节点和边的序列返回该路径、

  • path_seq 表示 nodeedge 的路径中的相对位置。

  • cost 是用于转到下一个节点的边的成本。

  • agg_cost 是从 startvid 到节点的成本。

如果没有路径,则结果集为空。

另请参阅

索引和表格