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

概述

最短路径快速算法（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] (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)
• 参数：

示例

示例图如下：

文件回写

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

直接返回

algo(sssp).params({
  uuids: 1,
  edge_schema_property: 'value',
  sssp_type: 'spfa',
  record_path: 0,
  direction: 'in'
}) as costs
return costs

结果：costs

algo(sssp).params({
  ids: 'A',
  edge_schema_property: '@default.value',
  sssp_type: 'spfa',
  direction: 'in',
  record_path: 1
}) as paths
return paths

结果：paths

流式返回

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

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