Dijkstra 最短路径¶
本文介绍 Dijkstra 最短路径算法，并演示如何用 GQL 实现该算法。
算法介绍¶
Dijkstra 最短路径用于在非负权图中计算源点到各可达点的最小路径代价。
该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。
更多信息，请参见 Dijkstra 最短路径。
数据模型¶
为了在 GQL 中实现 Dijkstra 最短路径算法，使用以下数据模型创建图类型：
- 实体由类型为
Node的点表示，点属性包括id和rating。 - 实体间关系由类型为
Link的边表示，边属性包括weight。
该图类型的完整定义，请参见准备图数据。
过程实现¶
为了计算 Dijkstra 最短路径结果，创建一个过程。
关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。
该过程接受以下输入参数：
source_id：INT64类型。 源点的 ID。target_id：INT64类型。 目标点的 ID。
此外，在过程内部定义了以下变量：
| 变量名 | 变量类型 | 描述 |
|---|---|---|
search_done |
原始值变量 | 标志 Dijkstra 搜索已终止。 |
has_path |
原始值变量 | 是否找到从源到目标的路径。 |
inf |
原始值变量 | 未初始化距离的无穷大哨兵值。 |
current_id |
原始值变量 | 当前正在确定的点 ID。 |
current_dist |
原始值变量 | 从源点到当前确定点的距离。 |
final_cost |
原始值变量 | 从源到目标的最短路径总代价。 |
walk_id |
原始值变量 | 逆向路径重建中使用的点 ID。 |
reverse_step |
原始值变量 | 逆向路径重建时的步骤计数。 |
path_len |
原始值变量 | 路径总长度（跳数）。 |
best_open |
全局 SumAgg 聚合值变量 | 选取下一个待确定点的最小堆条目。 |
pick_state |
全局 SumAgg 聚合值变量 | 当前正在确定的点状态。 |
back_state |
全局 SumAgg 聚合值变量 | 路径重建中使用的状态。 |
dist |
点绑定 SumAgg 聚合值变量 | 每点从源出发的暂定最短距离。 |
parent |
点绑定 SumAgg 聚合值变量 | 每点在最短路径上的父点。 |
edge_w |
点绑定 SumAgg 聚合值变量 | 每点在最短路径上的入边权重。 |
opened |
点绑定 SumAgg 聚合值变量 | 每点标志：该点在优先队列中。 |
settled |
点绑定 SumAgg 聚合值变量 | 每点标志：该点的距离已被确定。 |
cand |
点绑定 SumAgg 聚合值变量 | 当前扩展步骤中该点的最优松弛候选。 |
path_table |
表变量 | 存储逆序路径步骤的中间表。 |
以下步骤概述了该过程的逻辑：
- 将所有点的
dist初始化为无穷大；将源点的dist设为 0 并加入开放集。 - 反复从开放集中取出
dist最小的点（best_open）；若为目标点，记录final_cost并停止搜索。 - 对每条出边松弛邻居的
dist；若有改进，则更新dist、parent、edge_w并重新加入开放集。 - 通过
parent链从目标回溯到源点重建最短路径，返回有序路径步骤。
操作步骤¶
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。
1. 准备图数据¶
-
创建一个与数据模型匹配的图类型。
''' CREATE GRAPH TYPE IF NOT EXISTS dijkstra_shortest_path_graph_type AS { NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}), EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node) } ''' -
下载以下 CSV 文件，保留文件名，保存到部署目录下的
examples/algorithms/dijkstra_shortest_path/：查看 CSV 内容
dijkstra_shortest_path_node.csvid,rating 1,0 2,2 3,1 4,0 5,0 6,2 7,1 8,2 9,0 10,1 11,0 12,2 13,1 14,1 15,0 16,2 17,0 18,1 19,2 20,0 21,2 22,1 23,0 24,1dijkstra_shortest_path_edge.csvsrc_id,dst_id,weight 1,2,4 1,3,2 1,4,7 1,5,9 2,3,1 2,4,6 2,5,5 2,6,2 3,4,3 3,5,4 3,6,8 4,6,2 4,7,6 4,8,5 5,6,4 5,8,7 5,9,6 6,8,1 6,9,5 6,10,6 7,9,2 7,10,9 8,9,3 8,11,6 8,12,4 9,10,4 9,12,7 9,13,2 10,12,1 10,13,8 10,14,4 11,12,2 11,14,5 11,15,7 12,14,3 12,15,6 12,16,5 13,15,2 13,16,7 14,15,4 14,17,8 14,18,2 15,16,1 15,18,5 15,19,3 16,18,3 16,19,6 17,18,2 17,20,7 17,21,5 18,19,4 18,21,9 18,22,6 19,21,1 19,22,5 20,21,3 20,23,6 20,24,8 21,22,2 21,23,4 21,24,7 22,24,4 23,24,1 -
基于图类型创建临时图，并将数据文件加载到临时图中。
CREATE TEMPORARY GRAPH IF NOT EXISTS #dijkstra_shortest_path_graph TYPED dijkstra_shortest_path_graph_type''' USE #dijkstra_shortest_path_graph IMPORT INTO GRAPH { NODE (v@Node {id: id, rating: rating}) FROM DATAFILE { PATH: "file:///examples/algorithms/dijkstra_shortest_path/dijkstra_shortest_path_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE { PATH: "file:///examples/algorithms/dijkstra_shortest_path/dijkstra_shortest_path_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } '''导入成功后，在控制台执行以下查询核对点数：
''' USE #dijkstra_shortest_path_graph MATCH (n) RETURN count(n) AS node_count '''node_count应为24。点数不符时，先按文件问题排查检查文件和导入结果。
2. 创建过程¶
创建实现 Dijkstra 最短路径算法的过程。关于该过程的更多信息，请参见过程实现。
'''
CREATE OR REPLACE PROCEDURE dijkstra_shortest_path(
source_id INT64,
target_id INT64
)
RETURNS (step_no INT64, node_id INT64, parent_id INT64, edge_weight DOUBLE, path_cost DOUBLE, total_cost DOUBLE)
COMMENT "Compute the classic Dijkstra shortest path in a directed weighted graph whose vertex primary key is id and edge weight property is weight. Edge weights must be non-negative."
AS {
VALUE search_done BOOLEAN = false
VALUE has_path BOOLEAN = false
VALUE inf DOUBLE = 1000000000000000000.0
VALUE current_id INT64 = 0
VALUE current_dist DOUBLE = 0.0
VALUE final_cost DOUBLE = 0.0
VALUE walk_id INT64 = 0
VALUE reverse_step INT64 = 0
VALUE path_len INT64 = 0
VALUE best_open TopKAgg<1, dist DOUBLE ASC, node_id INT64 ASC>
VALUE pick_state TopKAgg<1, dist DOUBLE ASC, node_id INT64 ASC>
VALUE back_state TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>
NODE VALUE dist MinAgg<DOUBLE> = 1000000000000000000.0
NODE VALUE parent MinAgg<INT64> = 0
NODE VALUE edge_w MinAgg<DOUBLE> = 0.0
NODE VALUE opened OrAgg = false
NODE VALUE settled OrAgg = false
NODE VALUE cand TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>
TABLE path_table TYPED TABLE {
rev_step INT64,
node_id INT64,
parent_id INT64,
edge_weight DOUBLE,
path_cost DOUBLE
}
MATCH (n)
PER NODE (n) {
SET n.@dist = inf
SET n.@parent = 0
SET n.@edge_w = 0.0
SET n.@opened = false
SET n.@settled = false
SET n.@cand.clear()
}
MATCH (s)
WHERE s.id = source_id
PER NODE (s) {
SET s.@dist = 0.0
SET s.@parent = source_id
SET s.@edge_w = 0.0
SET s.@opened = true
SET s.@settled = false
}
WHILE search_done = false THEN {
SET @best_open.clear()
MATCH (n)
WHERE n.@opened = true AND n.@settled = false
PER NODE (n) {
SET @best_open += RECORD{dist: n.@dist, node_id: n.id}
}
IF @best_open.size() = 0 THEN {
SET search_done = true
}
ELSE {
SET current_id = @best_open.min().node_id
SET @pick_state.clear()
MATCH (u)
WHERE u.id = current_id
PER NODE (u) {
SET @pick_state += RECORD{dist: u.@dist, node_id: u.id}
SET u.@opened = false
SET u.@settled = true
}
SET current_dist = @pick_state.min().dist
IF current_id = target_id THEN {
SET final_cost = current_dist
SET has_path = true
SET search_done = true
}
ELSE {
MATCH (v)
WHERE v.@settled = false
PER NODE (v) {
SET v.@cand.clear()
}
MATCH (u)-[e]->(v)
WHERE u.id = current_id AND v.@settled = false
PER PATH {
VALUE tentative DOUBLE = 0.0
VALUE edge_cost DOUBLE = 0.0
SET edge_cost = CAST(e.weight AS DOUBLE)
SET tentative = current_dist + edge_cost
IF tentative < v.@dist THEN {
SET v.@cand += RECORD{
dist: tentative,
parent_id: current_id,
edge_weight: edge_cost
}
}
}
MATCH (v)
WHERE v.@settled = false AND v.@cand.size() > 0
PER NODE (v) {
SET v.@dist = v.@cand.min().dist
SET v.@parent = v.@cand.min().parent_id
SET v.@edge_w = v.@cand.min().edge_weight
SET v.@opened = true
}
}
}
}
IF has_path = true THEN {
SET walk_id = target_id
SET reverse_step = 0
WHILE walk_id <> source_id THEN {
SET @back_state.clear()
MATCH (n)
WHERE n.id = walk_id
PER NODE (n) {
SET @back_state += RECORD{
dist: n.@dist,
parent_id: n.@parent,
edge_weight: n.@edge_w
}
}
EXPORT
reverse_step,
walk_id,
@back_state.min().parent_id,
@back_state.min().edge_weight,
@back_state.min().dist
INTO path_table
SET walk_id = @back_state.min().parent_id
SET reverse_step = reverse_step + 1
}
SET @back_state.clear()
MATCH (n)
WHERE n.id = source_id
PER NODE (n) {
SET @back_state += RECORD{
dist: n.@dist,
parent_id: n.@parent,
edge_weight: n.@edge_w
}
}
EXPORT reverse_step, source_id, @back_state.min().parent_id, 0.0, @back_state.min().dist INTO path_table
SET path_len = reverse_step
}
FOR r IN path_table
RETURN
path_len - r.rev_step AS step_no,
r.node_id AS node_id,
r.parent_id AS parent_id,
r.edge_weight AS edge_weight,
r.path_cost AS path_cost,
final_cost AS total_cost
ORDER BY step_no ASC
}
'''
3. 调用过程¶
查找从点1到点24的路径，返回路径中的点、边权和累计代价。
USE #dijkstra_shortest_path_graph CALL dijkstra_shortest_path(1, 24) RETURN step_no, node_id, parent_id, edge_weight, path_cost, total_cost
返回：
展开查看返回
+---------+---------+-----------+-------------+-----------+------------+
| step_no | node_id | parent_id | edge_weight | path_cost | total_cost |
+---------+---------+-----------+-------------+-----------+------------+
| 0 | 1 | 1 | 0.0 | 0.0 | 23.0 |
| 1 | 2 | 1 | 4.0 | 4.0 | 23.0 |
| 2 | 6 | 2 | 2.0 | 6.0 | 23.0 |
| 3 | 8 | 6 | 1.0 | 7.0 | 23.0 |
| 4 | 9 | 8 | 3.0 | 10.0 | 23.0 |
| 5 | 13 | 9 | 2.0 | 12.0 | 23.0 |
| 6 | 15 | 13 | 2.0 | 14.0 | 23.0 |
| 7 | 19 | 15 | 3.0 | 17.0 | 23.0 |
| 8 | 21 | 19 | 1.0 | 18.0 | 23.0 |
| 9 | 23 | 21 | 4.0 | 22.0 | 23.0 |
| 10 | 24 | 23 | 1.0 | 23.0 | 23.0 |
+---------+---------+-----------+-------------+-----------+------------+
保存结果到文件或图中
如需将返回的结果保存为 CSV 文件或写入图，请参见 EXPORT。导出字段应与返回列及目标属性对应。