Skip to content

Latest commit

 

History

History
53 lines (28 loc) · 2.05 KB

01.Graph-Single-Source-Shortest-Path-01.md

File metadata and controls

53 lines (28 loc) · 2.05 KB

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 算法的实现代码