A* 最短路径¶
本文介绍 A* 最短路径算法，并演示如何用 GQL 实现该算法。
算法介绍¶
A* 最短路径通过启发式评分进行最佳优先搜索，以更高效地找到源点到目标点的路径。
该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。
更多信息，请参见 A* 最短路径。
数据模型¶
为了在 GQL 中实现 A* 最短路径算法，使用以下数据模型创建图类型：
- 实体由类型为
Node的点表示，点属性包括id和rating。 - 实体间关系由类型为
Link的边表示，边属性包括weight。
该图类型的完整定义，请参见准备图数据。
过程实现¶
为了计算 A* 最短路径结果，创建一个过程。
关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。
该过程接受以下输入参数：
source_id：INT64类型。 搜索起始点的 ID。target_id：INT64类型。 目标点的 ID。
此外，在过程内部定义了以下变量：
| 变量名 | 变量类型 | 描述 |
|---|---|---|
search_done |
原始值变量 | 标志 A* 搜索已终止。 |
has_path |
原始值变量 | 是否找到从源到目标的有效路径。 |
inf |
原始值变量 | 未初始化分数的无穷大哨兵值。 |
current_id |
原始值变量 | 当前步骤中正在扩展的点 ID。 |
current_g |
原始值变量 | 当前扩展点的 g 分数（从源出发的代价）。 |
final_cost |
原始值变量 | 找到的最短路径的总代价。 |
walk_id |
原始值变量 | 逆向路径重建时使用的点 ID。 |
reverse_step |
原始值变量 | 逆向路径重建时的步骤计数。 |
path_len |
原始值变量 | 找到路径的总步数。 |
best_open |
全局 SumAgg 聚合值变量 | 选取下一个待扩展点的最小堆条目（最小 f 分数）。 |
pick_state |
全局 SumAgg 聚合值变量 | 当前正在确定的点的状态快照。 |
back_state |
全局 SumAgg 聚合值变量 | 逆向路径重建中使用的状态。 |
heur |
点绑定 SumAgg 聚合值变量 | 每点到目标的 A* 启发值（h 分数）。 |
gscore |
点绑定 SumAgg 聚合值变量 | 每点从源出发的已知最小代价（g 分数）。 |
fscore |
点绑定 SumAgg 聚合值变量 | 每点 f 分数（g + h），用于开放集排序。 |
parent |
点绑定 SumAgg 聚合值变量 | 每点在当前最优路径上的父点 ID。 |
edge_w |
点绑定 SumAgg 聚合值变量 | 每点在最优路径上从父点到该点的边权。 |
opened |
点绑定 SumAgg 聚合值变量 | 每点标志：该点当前在开放集中。 |
closed |
点绑定 SumAgg 聚合值变量 | 每点标志：该点已被确定并移出开放集。 |
cand |
点绑定 SumAgg 聚合值变量 | 当前扩展中为该点找到的最优松弛候选。 |
path_table |
表变量 | 存储逆序路径步骤以供重建的中间表。 |
以下步骤概述了该过程的逻辑：
- 将所有点的
gscore初始化为无穷大；将源点的gscore设为 0，fscore设为其启发值heur，并加入开放集。 - 反复从开放集中取出
fscore最小的点（best_open）；若该点是目标点，则记录final_cost并停止搜索。 - 对每个邻居点，计算暂定 g 分数；若优于当前
gscore，则更新gscore、fscore、parent并重新加入开放集。 - 通过
parent链从目标回溯到源点重建路径，返回有序路径步骤。
操作步骤¶
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。
1. 准备图数据¶
-
创建一个与数据模型匹配的图类型。
''' CREATE GRAPH TYPE IF NOT EXISTS astar_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/astar_shortest_path/：查看 CSV 内容
astar_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,1astar_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 #astar_shortest_path_graph TYPED astar_shortest_path_graph_type''' USE #astar_shortest_path_graph IMPORT INTO GRAPH { NODE (v@Node {id: id, rating: rating}) FROM DATAFILE { PATH: "file:///examples/algorithms/astar_shortest_path/astar_shortest_path_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE { PATH: "file:///examples/algorithms/astar_shortest_path/astar_shortest_path_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } '''导入成功后，在控制台执行以下查询核对点数：
''' USE #astar_shortest_path_graph MATCH (n) RETURN count(n) AS node_count '''node_count应为24。点数不符时，先按文件问题排查检查文件和导入结果。
2. 创建过程¶
创建实现 A* 最短路径算法的过程。关于该过程的更多信息，请参见过程实现。
'''
CREATE OR REPLACE PROCEDURE astar_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 an A* shortest path in a directed weighted graph whose vertex primary key is id and edge weight property is weight. This demo version embeds the heuristic table for target_id = 24; other target values fall back to zero heuristic and therefore degrade toward Dijkstra."
AS {
VALUE search_done BOOLEAN = false
VALUE has_path BOOLEAN = false
VALUE inf DOUBLE = 1000000000000000000.0
VALUE current_id INT64 = 0
VALUE current_g 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, f DOUBLE ASC, node_id INT64 ASC>
VALUE pick_state TopKAgg<1, g DOUBLE ASC, f DOUBLE ASC, node_id INT64 ASC>
VALUE back_state TopKAgg<1, g DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>
NODE VALUE heur SumAgg<DOUBLE> = 0.0
NODE VALUE gscore MinAgg<DOUBLE> = 1000000000000000000.0
NODE VALUE fscore 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 closed OrAgg = false
NODE VALUE cand TopKAgg<1, f DOUBLE ASC, g 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.@heur = 0.0
SET n.@gscore = inf
SET n.@fscore = inf
SET n.@parent = 0
SET n.@edge_w = 0.0
SET n.@opened = false
SET n.@closed = false
SET n.@cand.clear()
}
IF target_id = 24 THEN {
MATCH (n)
PER NODE (n) {
IF n.id = 1 THEN {
SET n.@heur = 23.0
}
ELSEIF n.id = 2 THEN {
SET n.@heur = 19.0
}
ELSEIF n.id = 3 THEN {
SET n.@heur = 22.0
}
ELSEIF n.id = 4 THEN {
SET n.@heur = 19.0
}
ELSEIF n.id = 5 THEN {
SET n.@heur = 19.0
}
ELSEIF n.id = 6 THEN {
SET n.@heur = 17.0
}
ELSEIF n.id = 7 THEN {
SET n.@heur = 15.0
}
ELSEIF n.id = 8 THEN {
SET n.@heur = 16.0
}
ELSEIF n.id = 9 THEN {
SET n.@heur = 13.0
}
ELSEIF n.id = 10 THEN {
SET n.@heur = 16.0
}
ELSEIF n.id = 11 THEN {
SET n.@heur = 16.0
}
ELSEIF n.id = 12 THEN {
SET n.@heur = 15.0
}
ELSEIF n.id = 13 THEN {
SET n.@heur = 11.0
}
ELSEIF n.id = 14 THEN {
SET n.@heur = 12.0
}
ELSEIF n.id = 15 THEN {
SET n.@heur = 9.0
}
ELSEIF n.id = 16 THEN {
SET n.@heur = 12.0
}
ELSEIF n.id = 17 THEN {
SET n.@heur = 10.0
}
ELSEIF n.id = 18 THEN {
SET n.@heur = 10.0
}
ELSEIF n.id = 19 THEN {
SET n.@heur = 6.0
}
ELSEIF n.id = 20 THEN {
SET n.@heur = 7.0
}
ELSEIF n.id = 21 THEN {
SET n.@heur = 5.0
}
ELSEIF n.id = 22 THEN {
SET n.@heur = 4.0
}
ELSEIF n.id = 23 THEN {
SET n.@heur = 1.0
}
ELSEIF n.id = 24 THEN {
SET n.@heur = 0.0
}
}
}
MATCH (s)
WHERE s.id = source_id
PER NODE (s) {
SET s.@gscore = 0.0
SET s.@fscore = s.@heur
SET s.@parent = source_id
SET s.@edge_w = 0.0
SET s.@opened = true
SET s.@closed = false
}
WHILE search_done = false THEN {
SET @best_open.clear()
MATCH (n)
WHERE n.@opened = true AND n.@closed = false
PER NODE (n) {
SET @best_open += RECORD{f: n.@fscore, 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{g: u.@gscore, f: u.@fscore, node_id: u.id}
SET u.@opened = false
SET u.@closed = true
}
SET current_g = @pick_state.min().g
IF current_id = target_id THEN {
SET final_cost = current_g
SET has_path = true
SET search_done = true
}
ELSE {
MATCH (v)
PER NODE (v) {
SET v.@cand.clear()
}
MATCH (u)-[e]->(v)
WHERE u.id = current_id
PER PATH {
VALUE tentative DOUBLE = 0.0
VALUE edge_cost DOUBLE = 0.0
SET edge_cost = CAST(e.weight AS DOUBLE)
SET tentative = current_g + edge_cost
IF tentative < v.@gscore THEN {
SET v.@cand += RECORD{
f: tentative + v.@heur,
g: tentative,
parent_id: current_id,
edge_weight: edge_cost
}
}
}
MATCH (v)
WHERE v.@cand.size() > 0
PER NODE (v) {
SET v.@gscore = v.@cand.min().g
SET v.@fscore = v.@cand.min().f
SET v.@parent = v.@cand.min().parent_id
SET v.@edge_w = v.@cand.min().edge_weight
SET v.@opened = true
SET v.@closed = false
}
}
}
}
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{
g: n.@gscore,
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().g
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{
g: n.@gscore,
parent_id: n.@parent,
edge_weight: n.@edge_w
}
}
EXPORT reverse_step, source_id, @back_state.min().parent_id, 0.0, @back_state.min().g 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 #astar_shortest_path_graph CALL astar_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。导出字段应与返回列及目标属性对应。