单源最短路径

单源最短路径使用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

输入边表边的权重所在列。

使用示例

  1. 添加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;

    对应的数据结构图:

    image

  2. 添加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;
  3. 右击上一步的组件,选择查看数据 > 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            |