7.6 单源最短路径算法总结

liweiwei1419 ... 2021-12-11 图论
  • Dijkstra
About 1 min

# 有负权边的情况

有负权边的情况需要使用 Bellman-Ford 算法,Bellman-Ford 算法有一个基于队列的优化算法,叫 Shortest Path Faster Algorithm(SPFA),在《算法(第 4 版)》这本书上有介绍。

以后我们有机会再和大家做总结。

# 图论知识体系阶段总结(不全面)

# 最小生成树算法

理论基础 算法思想 数据结构 步骤
Prim 切分定理 动态规划 优先队列 11 个点开始,找到 v1v - 1 条边,不能形成环(不在树中)。
Kruskal 切分定理 贪心 并查集 从最短的边开始,一条一条添加,如果形成环,就丢弃。

# 最短路径算法

理论基础 用途 要求 算法思想 步骤
Dijkstra 松弛操作 求单源最短路径 不能有负权边 动态规划 1、找最短;2、确定一个解;3、更新。
Bellman-Ford 松弛操作 可以检测负权环,跑一遍可以得到负权环。 动态规划 对所有的边进行 v1v - 1 轮(最坏情况)松弛操作。
Floyd 松弛操作 求多源最短路径。 动态规划

说明:有负权环,对于求单源最短路径问题是没有意义的。

Last update: January 14, 2022 10:18
Contributors: suanfa8 , liweiwei1419