概述
单源最短路径问题(Single-Source Shortest Path, SSSP)计算的是从图中一个源节点到其余所有可达节点的最短路径。最短路径是指全部可能的路径中,所有边的权重和最小的路径;在无权图的情况下,是指边的数量最少的路径。最短路径的成本(或距离)是指所有边的权重和或数量。
Dijkstra(迪杰斯特拉)算法最初是由荷兰计算机科学家Edsger W. Dijkstra在1956年构思的,用于找到两个给定节点间的最短路径。单源最短路径是一种常见的变种,有助于进行有效的路径规划和网络分析。
基本概念
Dijkstra单源最短路径
我们将通过计算示例图中以b为源节点的无向加权最短路径来解释Dijkstra单源最短路径算法的基本实现:
1. 创建一个优先队列来存储节点及其与源节点之间的距离。初始化源节点的距离为0,其余节点为无穷大。所有节点标记为未访问。
![](https://img.ultipa.cn/draw/draw_4571683ba8384a1f966b9c8aedc12f2b.jpg?v='1689215708126')
2. 从队列中提取距离最小的节点,将其标记为已访问,对该节点的所有“未访问”邻居进行松弛操作。
![](https://img.ultipa.cn/draw/draw_f48205a154934dc7bee0a7a74a929206.jpg?v='1689215747833')
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,直到所有节点都被访问过。
![](https://img.ultipa.cn/draw/draw_703ab5f2ba344b6f9e98b4210edeb4dc.jpg?v='1689216069621')
dist(d) = min(1+3, ∞) = 4, dist(e) = min(1+4, ∞) = 5, dist(g) = min(1+2, ∞) = 3
![](https://img.ultipa.cn/draw/draw_f23e42fc70ce4a3199c214a95368ce91.jpg?v='1689216090060')
dist(d) = min(2+4, 4) = 4
![](https://img.ultipa.cn/draw/draw_d038072002da4439b2fbc941c8c1e41c.jpg?v='1689216106878')
dist(f) = min(3+5, ∞) = 8
![](https://img.ultipa.cn/draw/draw_fa3b39e312dc4ffd85483d35895ce796.jpg?v='1689216119382')
No neighbor can be relaxed
![](https://img.ultipa.cn/draw/draw_6269dd734f1847b6a9ac40366dbce51a.jpg?v='1689216255161')
dist(f) = min(5+8, 8) = 8
![](https://img.ultipa.cn/draw/draw_f9813078c9934fe689656ceb635ca931.jpg?v='1689216129914')
没有邻居可以被松弛
所有节点都访问过了,算法结束
特殊说明
- 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 |
/ | 是 | 按最短距离大小对结果进行排序 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_5428a498201d400ba015e05b2f4235f0.jpg?v='1691395226766')
文件回写
配置项 | 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 |