单源最短路径 - 人工智能平台 PAI

单源最短路径使用Dijkstra算法，用于查找从一个起始节点到所有其他节点的最短路径。单源最短路径组件能够输出起始节点到其他关联节点的最短路径及其数量。

配置组件

方法一：可视化方式

在Designer工作流页面添加单源最短路径组件，并在界面右侧配置相关参数：

参数类型	参数	描述
字段设置	选择源顶点列	边表的起点所在列。
	选择目标顶点列	边表的终点所在列。
	选择边权值列	边表边的权重所在列。
参数设置	起始节点 ID	用于计算最短路径的起始节点。
执行调优	进程数	作业并行执行的节点数。数字越大并行度越高，但是框架通讯开销会增大。
执行调优	进程内存	单个作业可使用的最大内存量，单位：MB，默认值为4096。如果实际使用内存超过该值，会抛出`OutOfMemory`异常。

方法二：PAI命令方式

使用PAI命令配置单源最短路径组件参数。您可以使用SQL脚本组件进行PAI命令调用，详情请参见场景4：在SQL脚本组件中执行PAI命令。

PAI -name SSSP
    -project algo_public
    -DinputEdgeTableName=SSSP_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=SSSP_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DstartVertex=a;

参数	是否必选	默认值	描述
inputEdgeTableName	是	无	输入边表名。
inputEdgeTablePartitions	否	全表读入	输入边表的分区。
fromVertexCol	是	无	输入边表的起点所在列。
toVertexCol	是	无	输入边表的终点所在列。
outputTableName	是	无	输出表名。
outputTablePartitions	否	无	输出表的分区。
lifecycle	否	无	输出表的生命周期。
workerNum	否	未设置	作业并行执行的节点数。数字越大并行度越高，但是框架通讯开销会增大。
workerMem	否	4096	单个作业可使用的最大内存量，单位：MB，默认值为4096。如果实际使用内存超过该值，会抛出`OutOfMemory`异常。
splitSize	否	64	数据切分的大小，单位：MB。
startVertex	是	无	起始节点ID。
hasEdgeWeight	否	false	输入边表的边是否有权重。
edgeWeightCol	否	无	输入边表边的权重所在列。

使用示例

添加SQL脚本组件，输入以下SQL语句生成训练数据。

drop table if exists SSSP_func_test_edge;
create table SSSP_func_test_edge as
select
    flow_out_id,flow_in_id,edge_weight
from
(
    select "a" as flow_out_id,"b" as flow_in_id,1.0 as edge_weight
    union all
    select "b" as flow_out_id,"c" as flow_in_id,2.0 as edge_weight
    union all
    select "c" as flow_out_id,"d" as flow_in_id,1.0 as edge_weight
    union all
    select "b" as flow_out_id,"e" as flow_in_id,2.0 as edge_weight
    union all
    select "e" as flow_out_id,"d" as flow_in_id,1.0 as edge_weight
    union all
    select "c" as flow_out_id,"e" as flow_in_id,1.0 as edge_weight
    union all
    select "f" as flow_out_id,"g" as flow_in_id,3.0 as edge_weight
    union all
    select "a" as flow_out_id,"d" as flow_in_id,4.0 as edge_weight
) tmp;

对应的数据结构图：

添加SQL脚本组件，输入以下PAI命令进行训练。

drop table if exists ${o1};
PAI -name SSSP
    -project algo_public
    -DinputEdgeTableName=SSSP_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=${o1}
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DstartVertex=a;

右击上一步的组件，选择查看数据 > SQL脚本的输出，查看训练结果。

| start_node | dest_node | distance | distance_cnt |
| ---------- | --------- | -------- | ------------ |
| a          | a         | 0.0      | 0            |
| a          | b         | 1.0      | 1            |
| a          | c         | 3.0      | 1            |
| a          | d         | 4.0      | 3            |
| a          | e         | 3.0      | 1            |