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

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

最短路径快速算法（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)

• 参数：

示例

示例图如下：

文件回写

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

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

流式返回

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

1--[101]--2--[104]--3
1--[101]--2--[105]--4
1--[101]--2
1--[101]--2--[103]--6