最短路算法
解决的问题
常常用于去解决在一个图当中,从一个顶点出发到达另一个顶点的最小路径权值总和求值。
前置知识点
* 图的基础知识
* 邻接矩阵/邻接表
* 贪心/枚举
最短路算法
* 单源最短路
* 从一个固定的起点出发,到达图上任意顶点的最短距离,如果我们将起点的顶点编号设置为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 队列来维护可能产生的顶点队列,在松弛的过程当中,不停的加入产生了变化且没有进入过队列的边,从而进行继续松弛,直到队列为空为止。
代码框架