企业官网建设流程全解析

单源最短路径

最短路径 (shortest paths)的相关实际场景比较广泛，比如地图、网络等。

单源最短路径 (SSSP / single-source shortest paths)是求解给定某一源点到其所有可达点的最短路径，即使得这些无权路径的边数或者带权路径的权重和最小。

Dijkstra (/ˈdaɪkstrə/) 算法解决的是非负权图的 SSSP，未使用堆查找优化时，也被称为 Dijkstra 暴力算法。Dijkstra 译作“迪杰斯特拉“。

松弛（Relax）

"松弛"这个术语在本章出现得较多，含义同数学意义上的松弛相同，减少约束。图的两点之间存在多条路径，找到最短的一条需要比较，每比较一次就减少一次约束。

上图表示在 SSSP 中，忽略原图中的其他点和边，探索过程中某一时刻点 A 对其邻接点的松弛。

红框中的下标：

• 第一个：在当前探索范围内，源点到该点的的距离。
• 第二个：相应路径上的父节点。和各顶点一样，都是实际以数字存储，-1 表示没有父节点。

观察 A B 两点状态，3 + 1 < 5，说明 A 点所处路径向 B 延伸后比此前源点到 B 的路径更短，松弛有效。

同理可得对 C 松弛有效，对 D 松弛无效。

如果之后某刻 A 点再次被有效松弛了，那么应该继续松弛 B C D 点。