● 【选择计算题】带权图的最短路径：求两个顶点间长度最短的路径。其中路径长度不是指路径上边数的总和，而是指路径上各边的权值总和；路径长度的具体含义取决于边上权值所代表的意义。
算法 | 描述 | |
1 | 迪杰斯特拉算法 | 主要用于求单源最短路径。按路径长度递增次序产生各顶点最短路径。 |
2 | 弗洛伊德算法 | 是一种动态规划算法，用于解决任意两点间的最短路径问题。 基本思路：通过枚举中间节点来逐步更新节点间的最短路径。 |
3 | 贝尔曼-福特算法 | 是一种用于解决带有负权边的最短路径问题的动态规划算法。可以求解从单个源节点到图中所有节点的最短路径，能够检测负权回路。 基本思路：利用松弛操作逐步更新每个节点的最短路径估计值，同时使用动态规划思想, 递推求解最短路径问题。 比迪杰斯特拉算法更通用，但时间复杂度较高，不适用于边数较多的情况 |
4 | A* (A-Star)算法 | 是一种启发式搜索算法。通过估计从当前节点到目标节点的最短距离来指导搜索方向，从而加快搜索速度。 时间复杂度与启发式函数有关。与迪杰斯特拉算法和贝尔曼-福特算法相比，能够更快找到最短路径，但计算启发式函数在某些情况下可能失效 |
5 | 约翰逊算法 | 是一种用于解决有向图上最短路径问题的算法，结合了迪杰斯特拉算法和贝尔曼-福特算法的优点 |
6 | SPFA算法 | 是一种用于解决带有负权边的图上最短路径问题的算法。基于贝尔曼-福特算法作改进，通过剪枝避免重复的松弛操作，使得时间复杂度比贝尔曼-福特算法更优，实际运行效率往往比较高。 |
理解：“松弛”就是不断用新发现的更短路径，去更新和放松当前记录的距离值。