7.6 单源最短路径算法总结

有负权边的情况

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

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

图论知识体系阶段总结（不全面）

最小生成树算法

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

最短路径算法

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

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