最短路径快速算法（SPFA）详解

最短路径快速算法（SPFA）详解

最短路径快速算法（SPFA）

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

概述

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

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

• F. Duan,关于最短路径的SPFA快速算法 About the SPFA algorithm

基本概念

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