单源最短路

所有边权都是正数 有环也不能用

朴素 Dijkstra 时间复杂是 O$\(n^2+m\)$, n 表示点数，m 表示边数
对于稠密图 效果好于堆优化版 稀疏图 堆优化版好于朴素版
朴素Dijkstra
堆优化版 Dijkstra 时间复杂度 $O\(mlog^n\)$, n 表示点数，m 表示边数
堆优化版
可以快速求出 起点到任一点的最短路 答案会存到dist数组中

存在负权边

Bellman-ford 算法 时间复杂度 $O(nm)$, n 表示点数，m 表示边数
可以求有边数限制的最短路，spfa是办不到的
Bellman-ford
SPFA 算法 时间复杂度 平均情况下 $O(m)$，最坏情况下 $O(nm)$, n 表示点数，m 表示边数
可以求有负权的最短路 还可以判断是否存在负环
可以快速求出 起点到任一点的最短路 答案会存到dist数组中
SPFA求最短路
SPFA判断负环

多源汇最短路

Flyod 算法 时间复杂度是 $O(n^3)$, n 表示点数
有负权也可以求 任意两点之间的最短路 基于动态规划思想
Flyod