最短路算法讲解
最短路算法的概念
顾名思义，就是求两个点间的最短（边权和或边数最小）路径的算法，注意此处的路径不能有重复走过的边。
最短路算法中的常见算法
FLOYD 算法
原理：通过类动态规划的方法，定义状态 f[i][j]为从 iii 点到 jjj 点的最短路，我们可以枚举中间点 kkk 表示以 kkk 为中间点的最短路，不难看出状态转移方程为 f[i][j] = min(f[i][j],f[i][k]+f[k][j]) ，注意初始将所有两点间距离设为 ∞\infty∞ ，∞\infty∞ 的实值自行确定，只要比所有边边权最大值大即可，个人建议设为 0x3f3f3f3f，存边时将对应边的距离设为对应边权。
时间复杂度：
O(n3)\operatorname{O}(n^3)O(n3) （若无特殊说明，下文中 nnn 默认表示节点数，mmm 默认表示边数，图默认是连通图）
空间复杂度：
O(n2)\operatorname{O}(n^2)O(n2)
优势：
1.是全源最短路，能求任意点间最短路径长度
2.代码简单
3.适用于绝大多数图
劣势：
1.时间复杂度、空间复杂度太大
参考代码：
DIJKSTRA 算法
原理：
我们先了解松弛操作：松弛操作就是看从源点到该点的最短路加该点到终点的边的边权有没有比源点到该点当前记录的最短路短，如果短就更新，例如目前从源点 111 到 点 555 的距离为 101010，点 555 到 点 666 的边的距离为 333 ，而当前记录的最短路距离为 151515 ，则将 151515 更新为 131313。
Dijkstra 的算法过程为：
1.将点集划分为 SSS 和 TTT 两个子集，SSS 里的节点为当前已有最短路的点， TTT 则是还没有最短路的点，同时定义 dis[u] 为源点到点 uuu 的距离
2.将源点加入 SSS 集合，将源点的 dis 设为 000，并找出和该点相连的所有邻接边中边权最小的边接的点，做松弛操作
3.重复上述过程，直到松弛不了
4.输出答案
这种贪心策略每次都选最小值，也会遍历和尝试松弛每个点，正确性显然，笔者不做证明。
由于上述操作中找最小值可以使用堆（优先队列，priority_queue）优化，下面的代码和时间复杂度分析对象都为堆优化 Dijkstra 算法。
时间复杂度：
O(mlogm)\operatorname{O}(m \log m)O(mlogm)
空间复杂度：
O(n)\operatorname{O}(n)O(n)
优势：
1.时间复杂度较低
2.容易理解
劣势：
1.只能用于非负权图
参考代码
最短路习题
【ACGO】A267.DJ舞池最强者---“斯特拉”
【洛谷】P1135 奇怪的电梯
【洛谷】P1144 最短路计数
【洛谷】P1807 最长路
【洛谷】P2865 [USACO06NOV] Roadblocks G
【洛谷】P6464 [传智杯 #2 决赛] 传送门
