7.6 单源最短路径算法总结
liweiwei1419 ... 2021-12-11 About 1 min
# 有负权边的情况
有负权边的情况需要使用 Bellman-Ford 算法,Bellman-Ford 算法有一个基于队列的优化算法,叫 Shortest Path Faster Algorithm(SPFA),在《算法(第 4 版)》这本书上有介绍。
以后我们有机会再和大家做总结。
# 图论知识体系阶段总结(不全面)
# 最小生成树算法
理论基础 | 算法思想 | 数据结构 | 步骤 | |
---|---|---|---|---|
Prim | 切分定理 | 动态规划 | 优先队列 | 从 个点开始,找到 条边,不能形成环(不在树中)。 |
Kruskal | 切分定理 | 贪心 | 并查集 | 从最短的边开始,一条一条添加,如果形成环,就丢弃。 |
# 最短路径算法
理论基础 | 用途 | 要求 | 算法思想 | 步骤 | |
---|---|---|---|---|---|
Dijkstra | 松弛操作 | 求单源最短路径 | 不能有负权边 | 动态规划 | 1、找最短;2、确定一个解;3、更新。 |
Bellman-Ford | 松弛操作 | 可以检测负权环,跑一遍可以得到负权环。 | 动态规划 | 对所有的边进行 轮(最坏情况)松弛操作。 | |
Floyd | 松弛操作 | 求多源最短路径。 | 动态规划 |
说明:有负权环,对于求单源最短路径问题是没有意义的。