01. 单源最短路径知识(一)
01. 单源最短路径知识(一)
1. 单源最短路径的定义
单源最短路径(Single Source Shortest Path):对于一个带权图
,其中每条边的权重是一个实数。另外,给定 中的一个顶点,称之为源点。则源点到其他所有各个顶点之间的最短路径长度,称为单源最短路径。
这里的路径长度,指的是路径上各边权之和。
单源最短路径问题的核心是找到从源点到其他各个顶点的路径,使得路径上边的权重之和最小。这个问题在许多实际应用中都非常重要,比如网络路由、地图导航、通信网络优化等。
常见的解决单源最短路径问题的算法包括:
- Dijkstra 算法:一种贪心算法,用于解决无负权边的情况。它逐步扩展当前已知最短路径的范围,选择当前距离起始节点最近的节点,并更新与该节点相邻的节点的距离。
- Bellman-Ford 算法:适用于有负权边的情况。它通过多次迭代来逐步逼近最短路径,每次迭代都尝试通过更新边的权重来缩短路径。
- 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 算法的实现代码
来源:https://github.com/itcharge/LeetCode-Py