最短路算法
解决的问题
常常用于去解决在一个图当中，从一个顶点出发到达另一个顶点的最小路径权值总和求值。
前置知识点
* 图的基础知识
* 邻接矩阵/邻接表
* 贪心/枚举
最短路算法
* 单源最短路
* 从一个固定的起点出发，到达图上任意顶点的最短距离，如果我们将起点的顶点编号设置为xxx,将任意顶点的编号设置为yyy，那么我们所求就是[x,1−>y][x,1 -> y][x,1−>y]的最短路径。
* 多源最短路
* 从任意一个起点出发，到达图上任意顶点的最短距离，我们将顶点数量最大设定为nnn，那么多源最短路所求的就是[1−>n,1−>n][1 -> n,1->n][1−>n,1−>n]的最短路径。
* 实现方式
* disdisdis数组与其含义:我们通常会定义一个disdisdis的数组，使顶点编号作为其disdisdis数组的对应下标，来保存其中[i,j][i,j][i,j]号顶点的之间的最短距离。
* **disdisdis数组的定义差异:**根据单源最短路和多源最短路的差异性(则起点是否为固定)，我们可以将disdisdis数组设置成（单源最短路）dis[j]dis[j]dis[j]或(多源最短路)dis[i][j]dis[i][j]dis[i][j]。
* 单源最短路由于起点是固定的，因此只需要一个下标jjj来表示终点的位置即可组成关系[i,j][i,j][i,j]，保存单个起点的最短路径权值总和。
* 而多源最短路由于起点不固定,所以我们需要两个下标i,ji,ji,j来组成关系，保存其两个顶点之间最短路径的权值总和。
松弛
松弛操作是所有最短路算法的核心思想，掌握了松弛，那么最短路算法的种类再多，也可以非常快速地理解。
操作方式:松弛就是以某一个顶点作为中转站，更新与这个顶点相邻的其他顶点的最短路径数值。 (我们把这种操作，称之为对于中转站顶点的松弛)。
多源最短路表达方式： 设定iii为当前路径起点，jjj为当前的路径终点,kkk为当前我们需要去松弛的顶点。
IFIFIF dis[i][j]<dis[i][k]+dis[k][j]dis[i][j] < dis[i][k] + dis[k][j]dis[i][j]<dis[i][k]+dis[k][j] : dis[i][j]=dis[i][k]+dis[k][j]dis[i][j] = dis[i][k] + dis[k][j]dis[i][j]=dis[i][k]+dis[k][j]
单源最短路表达方式: 在起点已经固定了的情况下，我们设置点jjj为当前路径终点，kkk为当前我们需要去松弛的顶点，已知dis[j]dis[j]dis[j]保存了起点到达jjj目前的最短距离，dis[k]dis[k]dis[k]保存了起点到达kkk的最短距离,w[k,j]w[k,j]w[k,j]表示顶点kkk到达jjj边的权值www，那么表达式为
IFIFIF dis[j]<dis[k]+w[k][j]dis[j] < dis[k] + w[k][j]dis[j]<dis[k]+w[k][j] : dis[j]dis[j]dis[j] = dis[k]+w[k][j]dis[k] + w[k][j]dis[k]+w[k][j]
FLOYD
核心思路
* 枚举任意一个顶点来作为即将要松弛的顶点。
* 遍历当前可以前往松弛顶点的其他顶点，作为起点。
* 遍历松弛顶点可以前往的顶点作为终点。
* 比较原先起点到终点的最短距离dis[i][j]dis[i][j]dis[i][j] 与经过松弛顶点的距离dis[i][k]+dis[k][j]dis[i][k] + dis[k][j]dis[i][k]+dis[k][j]作比较，取最小值更新最短距离。
因而，根据核心思路的先后顺序，可得出核心代码
DIJ
核心思想
由于是单源最短路算法，因此起点为固定的顶点。计算思维是根据贪心思想拓展而来，贪心策略为:遍历nnn次，每次选择距离起点最近的未遍历顶点作为下一个松弛的顶点，跟边的个数无关。因此Dij算法时间复杂度大多时候直接跟顶点总数挂钩。
无法处理负权边
DIJ优化
* 在Dij当中，我们为了寻找距离起点最近的顶点，通常需要使用for循环进行时间复杂度为O(n)O(n)O(n)的暴力枚举，这样的做法效率实在是过于低下，我们可以思考，有没有有一种容器，可以自动的将此时权值最小的顶点顶出来让我们自己使用呢？
* priority_queue 优先队列，优先队列可以设定排序规则，使其里面的元素按照某一种数值进行升序或者降序的排序，最值会作为队首拿出，每一次拿出插入的时间复杂度为O(logn)O(logn)O(logn)
* 假如，我们使用priority_queue来对搜索最近顶点的for循环进行替换，时间复杂度也就可以从O(n)−>O(logn)O(n) -> O(logn)O(n)−>O(logn)
BELLMAN - FORD最短路算法
单源最短路
核心思想:
枚举所有的边求最终的最小权值，准确的来说是枚举所有顶点的所有边，无视先后顺序，每当一次枚举的时候dis数组发生了改变，则进行下一次从头枚举，直到dis数组不再改变则结束。将dis数组不发生改变的这样的行为视为是枚举的终点，在这个终点为达到之前，会不停的从头遍历每一条边。
示范代码
SPFA
核心思想: BellMan-Ford算法在运行的过程当中，由于会对不会发生变化的边进行重复无意义的松弛 ，因此我们优化的策略就可以从这里入手，由 全部松弛 -> 只松弛可能产生变化的边，从而降低时间复杂度。
核心做法: queuequeuequeue 队列来维护可能产生的顶点队列，在松弛的过程当中，不停的加入产生了变化且没有进入过队列的边，从而进行继续松弛，直到队列为空为止。
代码框架
