单源最短路径问题

单源最短路径问题(Single Source Shortest Path,SSSP)指的是在一个 (Graph)中计算某个结点到其他结点的最短路径。

这里的 被定义为 $G=$,其中 $V$ 表示 结点(Vertex),$E$ 表示连接两个结点之间的 带权(Edge),$G$ 表示 (Graph)。

Dijkstra 算法

迪杰斯特拉算法Dijkstra's Algorithm)的核心思想是从起始点为中心向外层层扩展(BFS),直到找到终点。

其步骤如下:

  1. 初始化集合 S 表示已确定最短路径的结点(只有起始结点),初始化集合 U 保存未确定最短路径的结点(空集)。
  2. 遍历 U 中的所有结点,每次都挑选 距离起始结点最近的结点,将该结点移出集合 U,放入集合 S
  3. 重复第二步,直到遇见终止结点。

其中每次挑选最近的结点都需要计算起始结点到 U 中所有结点的距离,然而很多结点的距离在很多时候是不会变的,因此可以用一个最小堆来保存该距离,每次将结点从 U 取出放入 S 之后,根据以该结点为起始结点的边,更新 U 中的结点的最短距离。

优缺点如下:

  • (-) 无法处理 负的边权

优化

Floyd 算法

https://wiki.jikexueyuan.com/project/easy-learn-algorithm/floyd.html

优缺点如下:

*

优化

参考