Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/sssp/ Documentation version: v5.3.2 # 单源最短路径（SSSP） 本文介绍单源最短路径（Single-Source Shortest Paths, SSSP）算法，并演示如何用 GQL 实现。 ## 算法介绍 单源最短路径用于计算加权图中从给定源点到所有其他点的最短路径距离。当所有边的权重为非负时，经典解法有 [Dijkstra 算法](https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95)；在权重可能为负且不存在负权环（路径上的所有边的权重之和为负数）的情况下，适用 [Bellman–Ford 算法](https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95)。 本实现使用 Dijkstra 算法（要求边的权重为非负）。通过维护活动集，仅对活动集内点的出边执行边松弛，迭代更新点的距离，当某一轮无任何更新时终止。 1. 将每个点的临时距离初始化为”无穷大“，并将源点的距离设为`0`。 2. 反复对当前集合中点的出边执行松弛：对权重为`w`的边（`u -> v`），若`dist[u] + w < dist[v]`，则更新`dist[v]`并将`v`加入下一轮集合。 3. 当某一轮没有任何更新时停止。 更多 SSSP 信息，请参见[单源最短路径算法](https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98#%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E7%AE%97%E6%B3%95)。 ## 数据模型 为了用 GQL 实现 SSSP，将基于以下数据模型来创建图类型： - 用类型为`Place`的点表示位置。 - 用类型为`Connect`的有向边表示位置间连接，边上包含数值属性`distance`（边的权重）。 该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/sssp/#1_prepare_graph_data)。 ## 过程实现[]() 为计算图中从单一源点到所有点的最短路径距离，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)，以集合驱动的松弛方式实现 SSSP。 该过程的完整定义，请参见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/sssp/#2_create_a_procedure)。下文说明过程的关键组件及其工作原理。 该过程接收以下输入参数： - `s`：源点 ID。 此外，在过程内部定义了以下变量： | 变量 | 类型 | 说明 | `min_dist` | 点绑定 [MinAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/min_agg/) | 每个点的当前距离。初始化为一个较大的“无穷”值；源点的距离设为`0`。MinAgg 保证点保留目前为止的最小距离。 | `new_active` | 全局 [OrAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | 全局布尔标记，表示本轮是否发生距离更新；用于控制循环终止。 | `v_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 下一轮需要松弛其出边的点集合。 | `output_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 文件变量，用于指定文件以收集最终距离。 过程逻辑如下： 1. 将所有点的`min_dist`初始化为较大值；将源点的`min_dist`设为`0`，并将源点加入活动集`v_set`。 2. 当`new_active`为`true`时重复： 1. 将`new_active`置为`false`。 2. 对来自`v_set`中点`a`的每条边（`a -[e]-> b`），若`a.@min_dist` + `e.distance` < `b.@min_dist`，则更新`b.@min_dist`的值并将`new_active`置为`true`。 3. 将每个被更新的点`b`放入下一轮的`v_set`。 3. 收敛后（某一轮无更新），将每个点的 ID 和最终`min_dist`导出到`output_file`并返回结果（可按点 ID 排序）。 ## 操作步骤 在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。 ### 1. 准备图数据[]() 1. 创建与数据模型匹配的图类型。 ```` ''' CREATE GRAPH TYPE IF NOT EXISTS sssp_graph_type AS { NODE Place (LABEL Place {id INT PRIMARY KEY}), EDGE Connect (Place)-[LABEL Connect {distance INT, MULTIEDGE KEY ()}]->(Place) } ''' ```` 2. 下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/sssp/`： - [sssp_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/sssp/sssp_node.csv)：点数据。 - [sssp_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/sssp/sssp_edge.csv)：边数据。 查看 CSV 内容 sssp_node.csv ```` id 1 2 3 4 5 6 7 8 9 10 11 12 ```` sssp_edge.csv ```` src,dst,dist 1,2,3 1,3,4 2,3,2 1,9,9 1,7,9 7,9,2 3,7,1 2,6,999 3,5,1 3,8,1 5,6,2 5,11,5 6,10,1 10,11,1 ```` 3. 基于图类型创建临时图，并将数据文件加载到该临时图中。 ```` CREATE TEMPORARY GRAPH IF NOT EXISTS #sssp_graph TYPED sssp_graph_type ```` ```` ''' USE #sssp_graph IMPORT INTO GRAPH { NODE (v@Place {id: id}) FROM DATAFILE { PATH: "file:///examples/algorithms/sssp/sssp_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src)-[e@Connect{distance: dist}]->(id: dst) FROM DATAFILE { PATH: "file:///examples/algorithms/sssp/sssp_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } ''' ```` 导入成功后，在控制台执行以下查询核对点数： ```` ''' USE #sssp_graph MATCH (n) RETURN count(n) AS node_count ''' ```` `node_count`应为`12`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。 临时图`#sssp_graph`中的点关系如下图所示： [![analytic_wcc_algorithm_example](https://docs-cdn.nebula-graph.com.cn/figures/5.0/analytics/analytics-sssp-algorithm-example1.jpg)](https://docs-cdn.nebula-graph.com.cn/figures/5.0/analytics/analytics-sssp-algorithm-example1.jpg) 点关系示意图 ### 2. 创建过程[]() 创建一个过程以实现 SSSP 算法。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/sssp/#procedure_implement)。 ```` ''' CREATE OR REPLACE PROCEDURE sssp(s INT64) RETURNS () AS { NODE VALUE min_dist MinAgg = 10000000007 VALUE new_active OrAgg = true VALUE v_set ACTIVE_SET FILE output_file {id INT, min_dist INT}= DATAFILE { PATH: "file:///examples/algorithms/sssp/output", FORMAT: "CSV" } // 初始化源点 MATCH (a@Place) WHERE a.id = s PER NODE (a) { SET a.@min_dist = 0 } FINALLY { SET v_set = a } // 迭代直至无更新（收敛） WHILE @new_active = true THEN { SET @new_active = false MATCH (a@Place)-[e@Connect]-(b) WHERE a.@min_dist + e.distance < b.@min_dist AND a IN v_set PER PATH { SET b.@min_dist += a.@min_dist + e.distance // MinAgg 取最小值 SET @new_active += true // OrAgg 只要有更新即为 true } FINALLY { SET v_set = b } } // 收集结果 MATCH (a@Place) PER NODE (a) { EXPORT a.id, a.@min_dist INTO output_file } } ''' ```` ### 3. 调用过程 以源点`1`计算到各点的最短路径距离。 ```` USE #sssp_graph CALL sssp(1) FINISH ```` 此调用将结果写入 CSV，控制台不返回结果表。 在宿主机的部署目录下，打开`examples/algorithms/sssp/output/`中的 CSV 文件。示例内容如下： ```` "id","min_dist" 1,0 2,3 3,4 4,10000000007 5,5 6,7 7,5 8,5 9,7 10,8 11,9 12,10000000007 ```` `min_dist`表示从源点`1`出发、以`distance`属性作为边权重的最短路径长度。点`4`和`12`在该图中从点`1`不可达，显示为初始的“无穷”值（`10000000007`）。 以上结果与上方[点关系](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/sssp/#fig1)示意图一致。如图所示，例如，点`1`到点`5`的最短路径为`1 -> 3 -> 5`，距离为`5`。 [![analytic_wcc_algorithm_example](https://docs-cdn.nebula-graph.com.cn/figures/5.0/analytics/analytics-sssp-algorithm-example2.jpg)](https://docs-cdn.nebula-graph.com.cn/figures/5.0/analytics/analytics-sssp-algorithm-example2.jpg) 将结果写入图中 如果需要将 SSSP 结果持久化到图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)： - 先将 SSSP 输出字段导出到表变量（通常为`id`、`min_dist`）。 - 若写入远程图，使用`table_split(...)`分批，并通过`nebula_exec`批量执行`USE + INSERT`。 建议在目标图类型中为对应点类型（如`Place`）增加最短路径距离字段（如`min_dist`）。