修改密码

请输入密码
请输入密码 请输入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

      最短路径快速算法(SPFA)

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

      概述

      最短路径快速算法(Shortest Path Faster Algorithm, SPFA)是贝尔曼-福特(Bellman–Ford)算法的改进版本,用于计算图中源节点到所有可达节点的最短路径,即单源最短路径(Single-Source Shortest Paths, SSSP)。该算法适用于包含负权重边的图。

      SPFA算法最早由E.F. Moore于1959年发表,但“最短路径快速算法(SPFA)”这个名称是由FanDing Duan在1994年重新发现该算法时赋予的。

      基本概念

      SPFA

      给定一个图G=(V, E)和一个源节点s∈V,使用数组d[]来存储从s到所有节点的最短路径距离。初始化d[]中的所有元素为无穷大,除了d[s] = 0。

      SPFA的基本思想与贝尔曼-福特算法相同,即每个节点都被用作松弛其邻居节点的候选节点(Candidate)。相对于后者的改进在于,SPFA维护一个先进先出的队列Q来存储候选节点,并且只有被松弛的节点才会被添加到队列中。

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

      算法开始时,除了源节点,所有节点的距离都被设为无穷大,因此源节点被视为第一个被松弛并推入队列的节点。

      在每次迭代中,SPFA从队列Q中出队一个节点u作为候选节点。对于图中的每条边(u,v),如果节点v可以被松弛,则执行以下步骤:

      • 松弛节点v:d[v] = d[v] + w(u,v)。
      • 如果v不在队列Q中,则将节点v推入队列Q。

      一直重复这个过程,直到没有更多的节点可以被松弛。

      下面的步骤说明了SPFA如何计算以A为源节点的出边方向的带权最短路径:

      特殊说明

      • SPFA能够处理具有负权重边的图,前提是(1)源节点无法访问任何位于负循环(Negative Cycle)中的节点,以及(2)最短路径是有向的。负循环是指边权重之和为负的循环。如果存在负循环,或者存在负权重但最短路径是无向的,该算法将产生距离为无限的结果。这是因为算法会在负循环内或负边上反复遍历,导致每次的距离都不断减小。
      • 如果两个节点之间存在多条最短路径,算法会找出所有这些路径。
      • 在非连通图中,算法只输出源节点所在的连通分量内所有节点到源节点的最短距离。

      语法

      • 命令: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 spfa dijkstra 计算SPFA单源最短路径时,保持此项为spfa
      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',
        direction: 'out',
        sssp_type: 'spfa'
      }).write({
        file: {
          filename: 'costs'
        }
      })
      

      结果:文件costs

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

      结果:文件paths

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

      直接返回

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

      结果:costs

      _uuid totalCost
      1 0
      2 -2
      4 6
      6 4
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        sssp_type: 'spfa',
        direction: 'in',
        record_path: 1
      }) as paths
      return paths
      

      结果:paths

      1--[102]--6--[106]--4
      1--[102]--6
      1
      1--[102]--6--[103]--2

      流式返回

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

      结果:costs

      _uuid totalCost
      5 -3
      6 -4
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        sssp_type: 'spfa',
        direction: 'out',
        record_path: 1
      }).stream() as p
      where length(p) <> [0,3]
      return p
      

      结果:p

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