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 - 函数族¶

pgr_dijkstra` - Dijkstra 最短路径算法。
pgr_dijkstraCost` - 获取最短路径的总成本。
pgr_dijkstraCostMatrix - 使用 pgr_dijkstra 创建成本矩阵。
驾驶距离 - 使用 pgr_dijkstra 计算流域信息。
pgr_KSP - 使用 Yen 算法和 pgr_dijkstra 来获得 K 条最短路径。

建议

Warning

下一版本的拟议功能。

它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
- 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名字可能不会改变。（但仍然有可能改变）
- 签名可能不会改变。（但仍然有可能改变）
- 功能可能不会改变。（但仍然有可能改变）
- pgTap 测试已经完成。但可能需要更多。
- 文档可能需要完善。

pgr_dijkstraVia -拟议 - 获取一系列顶点的路径。
pgr_dijkstraNear - 拟议 - 获取到最近顶点的路线。
pgr_dijkstraNearCost - 拟议 - 获取最近顶点的成本。

介绍¶

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

主要特点是：

仅在具有正成本的边进行处理。
- 成本列上的负值被解释为边不存在。
当存在路径时返回值。
当没有路径时：
- 当起始顶点和结束顶点相同时。
  - 未包含值 $(v, v)$ 的 aggregate cost 为 $0$
- 当起始顶点和结束顶点不同且不存在路径时：
  - 未包含值 $(u, v)$ 的 aggregate cost 是 $\infty$
出于优化目的，起始顶点或结束顶点中的任何重复值都将被忽略。
运行时间： $O (| s t a r t v i d s | * (V \log V + 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( $s q l, s t a r t_{v i d}, e n d_{v i d}, d i r e c t e d$ )

其中 $s q l = {(i d_{i}, s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}, r e v e r s e_c o s t_{i})}$

和

$s o u r c e = ⋃ s o u r c e_{i}$ ,
$t a r g e t = ⋃ t a r g e t_{i}$ ,

图定义如下：

有向图

加权有向图， $G_{d} (V, E)$ 的定义如下：

顶点集 $V$
- $V = s o u r c e \cup t a r g e t \cup s t a r t_{v} v i d \cup e n d_{v i d}$
边集 $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

无向图

加权无向图， $G_{u} (V, E)$ 的定义如下：

顶点集 $V$
- $V = s o u r c e \cup t a r g e t \cup s t a r t_{v} v i d \cup e n d_{v i d}$
边集 $E$
- $E = {\begin{cases} {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} & if r e v e r s e_c o s t = \emptyset \\ {(s o u r c e_{i}, t a r g e t_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, c o s t_{i}) when c o s t >= 0} \\ \cup {(t a r g e t_{i}, s o u r c e_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} \\ \cup {(s o u r c e_{i}, t a r g e t_{i}, r e v e r s e_c o s t_{i}) when r e v e r s e_c o s t_{i} >= 0)} & if r e v e r s e_c o s t \neq \emptyset \end{cases}$

问题

给定：

$s t a r t_{v i d} \in V$ a starting vertex
$e n d_{v i d} \in V$ an ending vertex
$G (V, E) = {\begin{cases} G_{d} (V, E) & if6 d i r e c t e d = t r u e \\ G_{u} (V, E) & if5 d i r e c t e d = f a l s e \end{cases}$

然后：

$π = {(p a t h_s e q_{i}, n o d e_{i}, e d g e_{i}, c o s t_{i}, a g g_c o s t_{i})}$

其中：

$p a t h_s e q_{i} = i$
$p a t h_s e q_{| π |} = | π |$
$n o d e_{i} \in V$
$n o d e_{1} = s t a r t_{v i d}$
$n o d e_{| π |} = e n d_{v i d}$
$\forall i \neq | π |, (n o d e_{i}, n o d e_{i + 1}, c o s t_{i}) \in E$
$e d g e_{i} = {\begin{cases} i d_{(n o d e_{i}, n o d e_{i + 1}, c o s t_{i})} & when i \neq | π | \\ - 1 & when i = | π | \end{cases}$
$c o s t_{i} = c o s t_{(n o d e_{i}, n o d e_{i + 1})}$
$a g g_c o s t_{i} = {\begin{cases} 0 & when i = 1 \\ \sum_{k = 1}^{i} c o s t_{(n o d e_{k - 1}, n o d e_{k})} & when i \neq 1 \end{cases}$

换句话说：如果 $s t a r t_{v i d}$ 和 $e n d_{v i d}$ 之间存在最短路径，算法会根据节点和边的序列返回该路径、

$p a t h_s e q$ 表示 $n o d e$ 或 $e d g e$ 的路径中的相对位置。
$c o s t$ 是用于转到下一个节点的边的成本。
$a g g_c o s t$ 是从 $s t a r t_{v i d}$ 到节点的成本。

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

另请参阅¶

索引和表格