单源最短路径最短路径 (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 点。