修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

v5.0
搜索
    v5.0

      Delta-Stepping单源最短路径

      ✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

      概述

      单源最短路径问题(Single-Source Shortest Path, SSSP)计算的是从图中一个源节点到其余所有可达节点的最短路径。最短路径是指全部可能的路径中,所有边的权重和最小的路径;在无权图的情况下,是指边的数量最少的路径。最短路径的成本(或距离)是指所有边的权重和或数量。

      Delta-Stepping(增量步进)单源最短路径算法可以看成是 Dijkstra算法的一种变体,具有并行计算的潜力。

      算法的相关资料如下:

      基本概念

      Delta-Stepping单源最短路径

      Delta-Stepping单源最短路径算法引入了“桶”(Bucket)的概念,并且以一种更粗粒度的方式执行松弛操作。该算法利用一个增量参数delta (Δ) > 0来实现以下目标:

      • 维护一个数组B,其中B[i]包含距离在范围[iΔ, (i+1)Δ)内的节点。因此,Δ也被称为“步长”或“桶宽”。
      • 区分图中权重≤Δ的“轻边”(Light Edges)和权重>Δ的“重边”(Heavy Edges)。在松弛过程中,优先考虑轻边节点,因为它们的权重更低,更有可能产生较短的路径。

      松弛操作是指通过考虑经过节点u的路径,更新与节点u相连的节点v的距离,使其获得可能的更短距离。具体来说,节点v的距离会被更新为dist(v) = dist(u) + w(u,v),其中w(u,v)是边(u,v)的权重。此更新仅在当前dist(v)大于dist(u) + w(u,v)时进行。

      在Delta-Stepping单源最短路径算法中,松弛操作还包括根据更新后的距离值将被松弛的节点分配到相应的桶中。

      我们将通过计算示例图中以b为源节点的无向加权最短路径来解释Delta-Stepping单源最短路径算法的基本实现,设置Δ为3:

      1. 算法开始时,所有节点的距离都被设为无穷大,除了源节点,它的距离被设为0。将源节点分配到桶B[0]。

      2. 在每次迭代中,从第一个非空桶B[i]中移除所有节点:

      • 松弛所有被移除节点的轻边邻居,被松弛的节点可能被分配到B[i]或B[i+1]桶;推迟对重边邻居的松弛。
      • 如果B[i]中又有节点加入,重复上述操作直到B[i]为空。
      • 松弛所有推迟的重边邻居。
      从B[0]中移除节点b:
      松弛轻边邻居a为dist(a) = min(0+2,∞) = 2,d为dist(b) = min(0+3,∞) = 3

      从B[0]中移除节点a:
      轻边邻居b无法被松弛
      松弛重边邻居c为 dist(c) = min(0+5,∞) = 5,d无法被松弛

      3. 重复第2步,直到所有桶为空。

      从B[1]中移除节点d和c:
      松弛轻边邻居g为dist(g) = min(5+2,∞) = 7,b、c和d无法被松弛
      松弛重边邻居e为dist(e) = min(5+4,∞) = 9,a和b无法被松弛

      从B[2]中移除节点g:
      轻边邻居c无法被松弛
      松弛重边邻居f为dist(f) = min(7+5,∞) = 12

      从B[3]中移除节点e:
      松弛轻边邻居f为dist(f) = min(9+1,12) = 10

      从B[3]中移除节点f:
      轻边邻居e无法被松弛
      重边邻居g无法被松弛
      所有桶为空,算法结束

      通过将节点放入不同的桶进行并行处理,Delta-Stepping算法可以更有效地利用可用的计算资源,适用于大规模图和并行计算环境。

      特殊说明

      • Delta-Stepping单源最短路径算法适用于具有非负边权重的图。如果存在负权重,Delta-Stepping单源最短路径算法输出的结果也许是不正确的。这种情况建议使用SPFA算法。
      • 如果两个节点之间存在多条最短路径,算法会找出所有这些路径。
      • 在非连通图中,算法只输出源节点所在的连通分量内所有节点到源节点的最短距离。

      语法

      • 命令:algo(sssp)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      ids / uuids _id / _uuid / / 单个源节点的ID/UUID
      direction string in, out / 最短路径的方向,忽略则不考虑方向
      edge_schema_property []@schema?.property 数值类型,需LTE / 用作边权重的边属性,权重值为所有指定属性值的和;忽略则不考虑权重
      record_path int 0, 1 0 1代表返回最短路径,0代表返回最短距离
      sssp_type string delta_stepping dijkstra 计算增量步进单源最短路径时,保持此项为delta_stepping
      delta float >0 2 增量(delta)的值
      limit int ≥-1 -1 返回的结果条数,-1返回所有结果
      order string asc, desc / 按最短距离大小对结果进行排序

      示例

      示例图如下:

      文件回写

      配置项 record_path 回写内容 描述
      filename 0 _id,totalCost 从源节点到每个其他节点的最短距离/成本
      1 _id--_uuid--_id 从源节点到每个其他节点的最短路径,由构成路径的节点ID和边UUID交替出现表示
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'delta_stepping',
        delta: 2
      }).write({
        file: {
          filename: 'costs'
        }
      })
      

      结果:文件costs

      G,8
      F,4
      E,5
      D,5
      C,5
      B,2
      A,0
      
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'delta_stepping',
        delta: 2,
        record_path: 1
      }).write({
        file: {
          filename: 'paths'
        }
      })
      

      结果:文件paths

      A--[102]--F--[107]--E--[109]--G
      A--[102]--F--[107]--E
      A--[101]--B--[105]--D
      A--[101]--B--[104]--C
      A--[102]--F
      A--[101]--B
      A
      

      直接返回

      别名序号 record_path 类型 描述 列名
      0 0 []perNode 从源节点到每个其他节点的最短距离/成本 _uuid, totalCost
      1 []perPath 从源节点到每个其他节点的最短路径,由构成路径的节点和边的UUID交替出现表示 /
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'delta_stepping',
        delta: 2,
        order: 'desc'
      }) as costs
      return costs
      

      结果:costs

      _uuid totalCost
      7 8
      5 5
      4 5
      3 5
      6 4
      2 2
      1 0
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        direction: 'out',
        record_path: 1,
        sssp_type: 'delta_stepping',
        delta: 2,
        order: 'asc'
      }) as paths
      return paths
      

      结果:paths

      1
      1--[101]--2
      1--[102]--6
      1--[102]--6--[107]--5
      1--[101]--2--[105]--4
      1--[101]--2--[104]--3
      1--[102]--6--[107]--5--[109]--7

      流式返回

      别名序号 record_path 类型 描述 列名
      0 0 []perNode 从源节点到每个其他节点的最短距离/成本 _uuid, totalCost
      1 []perPath 从源节点到每个其他节点的最短路径,由构成路径的节点和边的UUID交替出现表示 /
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'delta_stepping'
      }).stream() as costs
      where costs.totalCost <> [0,5]
      return costs
      

      结果:costs

      _uuid totalCost
      6 4
      2 2
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'delta_stepping',
        record_path: 1
      }).stream() as p
      where length(p) <> [0,3]
      return p
      

      结果:p

      1--[102]--6--[107]--5
      1--[101]--2--[105]--4
      1--[101]--2--[104]--3
      1--[102]--6
      1--[101]--2
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写