概述
最短路径快速算法(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为源节点的出边方向的带权最短路径:
![](https://img.ultipa.cn/draw/draw_7b49715522cd46079f5c9f81f152083f.jpg?v='1689056307984')
特殊说明
- 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 |
/ | 是 | 按最短距离大小对结果进行排序 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_1f867733d9644c89bd785f5390e8e4fc.jpg?v='1691466119634')
文件回写
配置项 | 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 |