概述

单源最短路径问题（Single-Source Shortest Path, SSSP）计算的是从图中一个源节点到其余所有可达节点的最短路径。最短路径是指全部可能的路径中，所有边的权重和最小的路径；在无权图的情况下，是指边的数量最少的路径。最短路径的成本（或距离）是指所有边的权重和或数量。

Dijkstra（迪杰斯特拉）算法最初是由荷兰计算机科学家Edsger W. Dijkstra在1956年构思的，用于找到两个给定节点间的最短路径。单源最短路径是一种常见的变种，有助于进行有效的路径规划和网络分析。

基本概念

Dijkstra单源最短路径

我们将通过计算示例图中以b为源节点的无向加权最短路径来解释Dijkstra单源最短路径算法的基本实现：

1. 创建一个优先队列来存储节点及其与源节点之间的距离。初始化源节点的距离为0，其余节点为无穷大。所有节点标记为未访问。

2. 从队列中提取距离最小的节点，将其标记为已访问，对该节点的所有“未访问”邻居进行松弛操作。

松弛操作是指通过考虑经过节点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，直到所有节点都被访问过。

特殊说明

• Dijkstra算法适用于具有非负边权重的图。如果存在负权重，Dijkstra算法输出的结果也许是不正确的。这种情况建议使用 SPFA算法。
• 如果两个节点之间存在多条最短路径，算法会找出所有这些路径。
• 在非连通图中，算法只输出源节点所在的连通分量内所有节点到源节点的最短距离。

语法

• 命令：algo(sssp)
• 参数：

示例

示例图如下：

文件回写

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

直接返回

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'dijkstra',
  record_path: 0,
  order: 'desc'
}) as costs
return costs

结果：costs

algo(sssp).params({
  ids: 'A',
  edge_schema_property: '@default.value',
  direction: 'out',
  record_path: 1, 
  order: 'asc'
}) as paths
return paths

结果：paths

流式返回

algo(sssp).params({
  uuids: 1,
  edge_schema_property: '@default.value',
  sssp_type: 'dijkstra'
}).stream() as costs
where costs.totalCost <> [0,5]
return costs

结果：costs

algo(sssp).params({
  ids: 'A',
  edge_schema_property: '@default.value',
  record_path: 1
}).stream() as p
where length(p) <> [0,3]
return p

结果：p