最短路径算法
单源最短路算法
单源 -> 计算一个起点到达其他任意顶点的最短距离的算法 -> 单源最短路算法
多源最短路算法
多源 -> 计算任意顶点到达任意顶点的最短路径算法 -> 多源最短路算法
迪杰斯特拉算法
是 单源最短路算法
松驰
对于某一个顶点进行以下两种操作
1. *遍历 : 确定当前这个顶点的最短距离。// 请注意只在迪杰斯特拉当中有这样的效果
2. 修改: 修改邻接顶点距离起点的最短距离，当通过松弛的顶点到达相邻顶点的路径距离要小于原先到达该顶点的最短距离则可以修改起点到达该顶点的最短距离。
核心策略
思想： 贪心
依据: 当前顶点如果是距离起点最近的顶点的话，这就意味着没有任意一条路径经过其他顶点后到达该顶点的距离比原先距离还要小。
每次选择距离起点最近的顶点作为下一步要松驰的顶点，松驰的顶点的最短路径被确定，再去寻找下一个最短的顶点再去松弛。
关键代码
我们设定数组dis[x]代表了顶点x距离起点的最小距离
我们设定数组vis[x]代表顶点x是否被标记过，true代表松驰过，false代表没有
数组mp[x][y]代表顶点x与y的边的权值
1.
目的: 找到当前距离起点最近的并且没有被松弛过的顶点。
2. 松弛这个顶点 ，遍历这个顶点
3. 查找与pos相临的顶点，查看是否需要经过pos到达这些顶点使得他们的最短距离变小
最终这样的代码需要执行n-1次，对n-1个顶点进行松弛后得到起点到达任意顶点的最短距离。
贝尔曼-福德 斯帕夫
属于单源最短路算法。
注： 任何算法执行的时候都是根据他的算法执行策略(算法思想)执行的，他可以产出一段保证某种性质的数据。
例: 这是一个单源最短路算法，所以他产出的数据是 - 起点到达任意顶点的最短路径。
贝尔曼福德与斯帕夫可以去处理 负权边 的情况。
值得注意的是，迪杰斯塔拉处理不了负权边的情况。
*负权边: 顶点A与顶点B的边的权值为负数的情况。
算法执行策略 - 算法规则
核心思想 : 枚举
对于贝尔曼福德来说，每一个顶点的最短距离是否确定不是根据他是否被松弛过，而是根据他自身的最短路径在本轮松弛当中是否产生变化。
从起点开始进行松弛，假若相临顶点的最短距离发生变化，那么就去遍历发生变化的顶点无关远近。
也就是说，只要还有顶点的最短距离dis[x]产生变化，那么贝尔曼福德就会无休止的松弛下去。
直到没有任何顶点的最短距离在发生变化后，贝尔曼福德才会停下，此时才得到最短距离答案。
时间复杂度
O(n×m)O(n \times m)O(n×m)
每一轮对于全部顶点的松弛他可以确定至少一个顶点的最短距离。
贝尔曼福德的三步骤实现
1. 松弛所有的顶点，修改所有顶点相临的最短距离
2. 检测是否有顶点的最短距离发生改变，如果有，那么回到操作1在执行一遍，如果没有，来到操作3
3. 退出循环，得到最短路径数组dis
贝尔曼福德的缺点
当一个顶点的最短路值发生改变之后，整个矩阵的顶点的最短路径你都需要重新松弛，这样会造成非常多的不必要的顶点松弛，为了避免这样的情况，我们可以去进行优化。
优化点: 将 全部顶点松弛 -> 只对发生改变的顶点进行松弛
需要去解决的问题: 保存发生改变的顶点，针对性的进行松弛。
使用容器queuequeuequeue，来保存发生改变的顶点。
1. 将起点加入queue
2. 取出队首进行松弛，如果有顶点的最短路数值发生改变则把顶点加入队列。
3. 如果队列不为空，则返回操作2继续执行，否则退出获得最短路数组dis。
这样优化后的算法，我们把他称之为是SPFA- 斯帕夫。
