Dijkstra - 函数族

建议

Warning

下一版本的拟议功能。

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

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

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

    • 名字可能不会改变。（但仍然有可能改变）

    • 签名可能不会改变。（但仍然有可能改变）

    • 功能可能不会改变。（但仍然有可能改变）

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

    • 文档可能需要完善。

介绍

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

主要特点是：

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

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

  • 当存在路径时返回值。

  • 当没有路径时：

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

      • 未包含值 \((v, v)\) 的 aggregate cost 为 \(0\)

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

      • 未包含值 \((u, v)\) 的 aggregate cost 是 \(\infty\)

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

  • 运行时间： \(O(| start\ vids | * (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(\(sql, start_{vid}, end_{vid}, directed\))

其中 \(sql =\{(id_i, source_i, target_i, cost_i, reverse\_cost_i)\}\)

和

  • \(source = \bigcup source_i\),

  • \(target = \bigcup target_i\),

图定义如下：

有向图

加权有向图， \(G_d(V,E)\) 的定义如下：

  • 顶点集 \(V\)

    • \(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)

  • 边集 \(E\)

    • \(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \quad \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i>=0 \} & \quad \text{if } reverse\_cost \neq \varnothing \\ \end{cases}\)

无向图

加权无向图， \(G_u(V,E)\) 的定义如下：

  • 顶点集 \(V\)

    • \(V = source \cup target \cup {start_v{vid}} \cup {end_{vid}}\)

  • 边集 \(E\)

    • \(E = \begin{cases} \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \quad \text{ if } reverse\_cost = \varnothing \\ \text{ } \text{ } & \text{ } \\ \text{ } \{(source_i, target_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, cost_i) \text{ when } cost >=0 \} & \text{ } \\ \cup \{(target_i, source_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \text{ } \\ \cup \{(source_i, target_i, reverse\_cost_i) \text{ when } reverse\_cost_i >=0)\} & \quad \text{ if } reverse\_cost \neq \varnothing \\ \end{cases}\)

问题

给定：

  • \(start_{vid} \in V\) a starting vertex

  • \(end_{vid} \in V\) an ending vertex

  • \(G(V,E) = \begin{cases} G_d(V,E) & \quad \text{ if6 } directed = true \\ G_u(V,E) & \quad \text{ if5 } directed = false \\ \end{cases}\)

然后：

  • \(\boldsymbol{\pi} = \{(path\_seq_i, node_i, edge_i, cost_i, agg\_cost_i)\}\)

其中：

  • \(path\_seq_i = i\)

  • \(path\_seq_{| \pi |} = | \pi |\)

  • \(node_i \in V\)

  • \(node_1 = start_{vid}\)

  • \(node_{| \pi |} = end_{vid}\)

  • \(\forall i \neq | \pi |, \quad (node_i, node_{i+1}, cost_i) \in E\)

  • \(edge_i = \begin{cases} id_{(node_i, node_{i+1},cost_i)} &\quad \text{when } i \neq | \pi | \\ -1 &\quad \text{when } i = | \pi | \\ \end{cases}\)

  • \(cost_i = cost_{(node_i, node_{i+1})}\)

  • \(agg\_cost_i = \begin{cases} 0 &\quad \text{when } i = 1 \\ \displaystyle\sum_{k=1}^{i} cost_{(node_{k-1}, node_k)} &\quad \text{when } i \neq 1 \\ \end{cases}\)

换句话说：如果 \(start_{vid}\) 和 \(end_{vid}\) 之间存在最短路径，算法会根据节点和边的序列返回该路径、

  • \(path\_seq\) 表示 \(node\) 或 \(edge\) 的路径中的相对位置。

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

  • \(agg\_cost\) 是从 \(start_{vid}\) 到节点的成本。

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

另请参阅

索引和表格