单源最短路径（SSSP）¶

本文介绍单源最短路径（Single-Source Shortest Paths, SSSP）算法，并演示如何用 GQL 实现。

算法介绍¶

单源最短路径用于计算加权图中从给定源点到所有其他点的最短路径距离。当所有边的权重为非负时，经典解法有 Dijkstra 算法；在权重可能为负且不存在负权环（路径上的所有边的权重之和为负数）的情况下，适用 Bellman–Ford 算法。

本实现使用 Dijkstra 算法（要求边的权重为非负）。通过维护活动集，仅对活动集内点的出边执行边松弛，迭代更新点的距离，当某一轮无任何更新时终止。

将每个点的临时距离初始化为”无穷大“，并将源点的距离设为0。
反复对当前集合中点的出边执行松弛：对权重为w的边（u -> v），若dist[u] + w < dist[v]，则更新dist[v]并将v加入下一轮集合。
当某一轮没有任何更新时停止。

更多 SSSP 信息，请参见单源最短路径算法。

数据模型¶

为了用 GQL 实现 SSSP，将基于以下数据模型来创建图类型：

用类型为Place的点表示位置。
用类型为Connect的有向边表示位置间连接，边上包含数值属性distance（边的权重）。

该图类型的完整定义，请参见准备图数据。

过程实现 ¶

为计算图中从单一源点到所有点的最短路径距离，创建一个过程，以集合驱动的松弛方式实现 SSSP。

该过程的完整定义，请参见创建过程。下文说明过程的关键组件及其工作原理。

该过程接收以下输入参数：

s：源点 ID。

此外，在过程内部定义了以下变量：

变量	类型	说明
`min_dist`	点绑定 MinAgg 聚合值变量	每个点的当前距离。初始化为一个较大的“无穷”值；源点的距离设为`0`。MinAgg 保证点保留目前为止的最小距离。
`new_active`	全局 OrAgg 聚合值变量	全局布尔标记，表示本轮是否发生距离更新；用于控制循环终止。
`v_set`	活动集变量	下一轮需要松弛其出边的点集合。
`output_file`	文件变量	文件变量，用于指定文件以收集最终距离。

过程逻辑如下：

将所有点的min_dist初始化为较大值；将源点的min_dist设为0，并将源点加入活动集v_set。
当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。
收敛后（某一轮无更新），将每个点的 ID 和最终min_dist导出到output_file并返回结果（可按点 ID 排序）。

操作步骤¶

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

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)
}
'''

下载以下 CSV 文件，保留文件名，保存到部署目录下的examples/algorithms/sssp/：
- sssp_node.csv：点数据。
- 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
```

基于图类型创建临时图，并将数据文件加载到该临时图中。

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。点数不符时，先按文件问题排查检查文件和导入结果。

临时图#sssp_graph中的点关系如下图所示：

2. 创建过程 ¶

创建一个过程以实现 SSSP 算法。关于该过程的更多信息，请参见过程实现。

'''
CREATE OR REPLACE PROCEDURE sssp(s INT64) RETURNS () AS {
    NODE VALUE  min_dist        MinAgg<INT> = 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）。

以上结果与上方点关系示意图一致。如图所示，例如，点1到点5的最短路径为1 -> 3 -> 5，距离为5。

将结果写入图中

如果需要将 SSSP 结果持久化到图，请参见 EXPORT：

先将 SSSP 输出字段导出到表变量（通常为id、min_dist）。
若写入远程图，使用table_split(...)分批，并通过nebula_exec批量执行USE + INSERT。

建议在目标图类型中为对应点类型（如Place）增加最短路径距离字段（如min_dist）。