单源最短路径知识（一）

1. 单源最短路径的定义

单源最短路径（Single Source Shortest Path）：对于一个带权图 $G = (V, E)$，其中每条边的权重是一个实数。另外，给定 $v$ 中的一个顶点，称之为源点。则源点到其他所有各个顶点之间的最短路径长度，称为单源最短路径。

这里的路径长度，指的是路径上各边权之和。

单源最短路径问题的核心是找到从源点到其他各个顶点的路径，使得路径上边的权重之和最小。这个问题在许多实际应用中都非常重要，比如网络路由、地图导航、通信网络优化等。

常见的解决单源最短路径问题的算法包括：

1. Dijkstra 算法：一种贪心算法，用于解决无负权边的情况。它逐步扩展当前已知最短路径的范围，选择当前距离起始节点最近的节点，并更新与该节点相邻的节点的距离。
2. Bellman-Ford 算法：适用于有负权边的情况。它通过多次迭代来逐步逼近最短路径，每次迭代都尝试通过更新边的权重来缩短路径。
3. SPFA 算法：优化的 Bellman-Ford 算法，它在每次迭代中不遍历所有的边，而是选择性地更新与当前节点相关的边，从而提高了算法的效率。

这些算法根据图的特点和问题的需求有所不同，选择适合的算法可以在不同情况下有效地解决单源最短路径问题。

2. Dijkstra 算法

2.1 Dijkstra 算法的算法思想

Dijkstra 算法的算法思想：通过逐步选择距离起始节点最近的节点，并根据这些节点的路径更新其他节点的距离，从而逐步找到最短路径。

2.2 Dijkstra 算法的实现步骤

2.3 Dijkstra 算法的实现代码

3. Bellman-Ford 算法

3.1 Bellman-Ford 算法的算法思想

3.2 Bellman-Ford 算法的实现步骤

3.3 Bellman-Ford 算法的实现代码

4. SPFA 算法

4.1 SPFA 算法的算法思想

4.2 SPFA 算法的实现步骤

4.3 SPFA 算法的实现代码