修改密码

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

      Dijkstra单源最短路径

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

      概述

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

      Dijkstra(迪杰斯特拉)算法最初是由荷兰计算机科学家Edsger W. Dijkstra在1956年构思的,用于找到两个给定节点间的最短路径。单源最短路径是一种常见的变种,有助于进行有效的路径规划和网络分析。

      基本概念

      Dijkstra单源最短路径

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

      1. 创建一个优先队列来存储节点及其与源节点之间的距离。初始化源节点的距离为0,其余节点为无穷大。所有节点标记为未访问。

      2. 从队列中提取距离最小的节点,将其标记为已访问,对该节点的所有“未访问”邻居进行松弛操作。

      访问节点b:
      dist(a) = min(0+2,∞) = 2, dist(c) = min(0+1,∞) = 1

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

      一旦节点被标记为已访问,其最短路径就被确定了,其距离在算法的余下过程中将不再改变。算法仅更新尚未访问过的节点的距离。

      3. 重复步骤2,直到所有节点都被访问过。

      访问节点c:
      dist(d) = min(1+3, ∞) = 4, dist(e) = min(1+4, ∞) = 5, dist(g) = min(1+2, ∞) = 3

      访问节点a:
      dist(d) = min(2+4, 4) = 4

      访问节点g:
      dist(f) = min(3+5, ∞) = 8

      访问节点d:
      No neighbor can be relaxed

      访问节点e:
      dist(f) = min(5+8, 8) = 8

      访问节点f:
      没有邻居可以被松弛
      所有节点都访问过了,算法结束

      特殊说明

      • Dijkstra算法适用于具有非负边权重的图。如果存在负权重,Dijkstra算法输出的结果也许是不正确的。这种情况建议使用 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 dijkstra dijkstra 计算Dijkstra单源最短路径时,保持此项为dijkstra
      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'
      }).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: 'dijkstra',
        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: 'dijkstra',
        record_path: 0,
        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({
        ids: 'A',
        edge_schema_property: '@default.value',
        direction: 'out',
        record_path: 1, 
        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: 'dijkstra'
      }).stream() as costs
      where costs.totalCost <> [0,5]
      return costs
      

      结果:costs

      _uuid totalCost
      6 4
      2 2
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        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
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写