笔记3：最短路
Social_Zhao · · 个人记录
笔记3：最短路
前言：
没有前言(⊙o⊙)...
补充：
首先你要知道一个事实：如果图中有一个环，这个环上所有边权加起来是负数（简称负环），则不存在最短路。（你可以绕着这个环一直走下去，越走越短）
在开始之前，我需要介绍一个东西：三角形不等式
众所周知，三角形两边之和大于第三边。用不等式可以表示为
下文提到的松弛操作全部与此有关
正文：
最短路的求法有以下几种：
然而鲁迅说过，其实世上本没有路，走的人多了，也便成了路
于是现在就有了另一条路，可以直接从
显然图上的三个箭头的长度满足三角形不等式，故
AB+BC<AC
因此你就会改变你原来的想法，不走
这就叫松弛操作
1、关于Floyd 算法
主要思想：
时间复杂度：
对图的要求：没有负环
本算法只适用于邻接矩阵，可以一次性求出所有点对间的最短路。
算法过程：
先初始化所有点自己到自己的距离为0，每条边的起点到终点的距离为边权，其他INF，然后枚举开始点，中间点以及结束点。以刚才的图为例，如果现在经过草坪中的一个点k，距离就会比老老实实走大路短，就选择踩草坪而不是走大路。故状态转移方程为
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
特别需要注意的是，
代码：
void floyd() {
for(int i=1;i<=n;i++) //初始化
{
for(int j=1;j<=n;j++)
{
if(i==j) dis[i][j]=0; //自己到自己距离为0
else if(a[i][j]) dis[i][j]=a[i][j]; //如果两点间直接相连，则设为边权
else dis[i][j]=0x7fffff/2; //其他赋极大值
}
}
//算法主干：
for(int k=1;k<=n;k++) //枚举中间点
for(int i=1;i<=n;i++) //枚举起点
for(int j=1;j<=n;j++) //枚举终点
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); //状态转移
}本算法的优点和缺点：
-
优点：简单好写，可以快速求所有点对最短路径
-
缺点：慢，而且在单源最短路中很浪费
2、关于
Dijkstra 算法：一种不好卡的算法（极快）
主要思想：贪心（多么强大啊）
对图的要求：
快也是有代价的，不能处理负权时间复杂度：朴素
O(n^2) ，堆优化O((n+m)logm) 可以用邻接矩阵或前向星，本文主要讨论前向星，每次只能求单源最短路，若要求所有点对最短路，就要调用N次。
本算法使用蓝白点思想，将图中的点分为蓝点（已确定最短路）和白点（未确定最短路）
算法过程（重点）：
首先初始化到源点的距离为0，其他所有点的距离为无穷大。
经过如下n次操作
每次选出目前距离最短的白点，并标记它为蓝点，对周围的点进行松弛
对
Dijkstra 算法正确性的证明(看不懂可以跳过)：反证法：
如果每次选出的点到原点距离(记为
dis[now] )（目前最短）还可以继续松弛，则必存在源点到另一个点的距离(记为dis[x] )加上这两点之间一条边的权值小于dis[now] 。记为dis[x]+d<dis[now] 由于
dis[x],d 都是非负数，故dis[x] 小于dis[now] 。因此
dis[now] 不是目前最短的边，与之前的题设（dis[now] 最短）矛盾故
dis[now] 一定是最短路证毕
代码：
朴素算法
O(n^2) 代码:void dijkstra(int source) { memset(vis,0,sizeof(vis)); //目前所有点都是蓝点 memset(dis,0x3f,sizeof(dis)); //到每个点的距离都是无穷大（未确定） dis[source]=0; //源点距离为0 for(int i=1;i<=n;i++) { int minn=0x3f3f3f3f,x; for(int j=1;j<=n;j++) { if(dis[j]<minn&&!vis[j]) minn=dis[j],x=j; //选出dis最小的白点 } vis[x]=1; //标记为蓝点 for(int j=head[x];j;j=edge[j].next) //依次松弛 { int y=edge[j].to,z=edge[j].dis; if(dis[x]+z<dis[y]) dis[y]=dis[x]+z } } }不难发现，在寻找dis最小点的时候，可以使用堆优化，故
void dijkstra(int source) { priority_queue<pair<int,int> >q;//大根堆，通过取相反数变成小根堆 memset(vis,0,sizeof(vis)); //目前所有点都是蓝点 memset(dis,0x3f,sizeof(dis)); //到每个点的距离都是无穷大（未确定） dis[source]=0; //源点距离为0 q.push(make_pair(0,source)); //将源点入堆 while(q.size()) //还有白点时 { int x=q.top().second;q.pop(); //取出dis最小的点O(logn) if(vis[x]) continue; //如果是蓝点就退出 vis[x]=1; //标记为蓝点 for(int j=head[x];j;j=edge[j].next) //依次松弛 { int y=edge[j].to,z=edge[j].dis; if(dis[x]+z<dis[y]) { dis[y]=dis[x]+z; q.push(make_pair(-dis[y],y)); //入堆 } } } }本算法的优点和缺点：
-
优点：不会被卡
-
缺点：不能处理负权，没有扩展用途。
3、关于
Bellman-ford 算法：这是一种处于过渡期的算法，它也不会被卡，因为它本来就慢得要死，没人会卡它
（Bellman-ford：QAQ）主要思想：没有什么特别的思想
由于算法的思路需要，前向星中要多存每条边的起点
对图的要求：无负环
算法过程：
初始化同
dijkstra 算法然后反复对每条边连着的点进行松弛，使之逐渐逼近最短路。
另外，本算法可以判负环：如果像上面那样松弛完后还能松弛，那就说明你再怎么松弛都不会有用的，因为有负环。
算法不常见，所以直接（别怪我不负责啊）
代码：
bool bellman(int source) { for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f; dis[source]=0; //初始化 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) //反复松弛 if(dis[edge[j].from]+edge[j].dis<=dis[edge[j].to]) { dis[edge[j].to]=dis[edge[j].from]+edge[j].dis; } for(int i=1;i<=m;i++) if(dis[edge[i].from]+edge[i].dis<=dis[edge[i].to]) return 0; //判负环 return 1; }对于过渡期的算法，我们不多谈它的优缺点。因为它有一个更好的版本：
4、关于
SPFA 算法它已经死了
在NOI2018 T1：归程中，一位同学熟练地使用
SPFA 求了最短路，结果呢？100->60$，$AU->CU 下面是正题： $SPFA$算法其实是$Bellman-Ford$算法的队列优化版本 时间复杂度：$O(km)$ (K是常数，**平均值**为2) 对图的要求：无负环 #### 算法过程： 同上初始化，这时新建一个队列，将源点入队，且标记它在队列中 取出队首，对周围的点进行松弛，如果目标点不在队列中，就将其入队 这么做直到队列为空 与$Bellman-Ford$算法一样，$SPFA$也可以判负环，如果一个点弹出队列超过N-1次，则有负环 #### 代码： ```cpp void spfa(int source) { queue<int> q; memset(dis,ox3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[source]=0,vis[source]=1; q.push(source); while(q.size()) { int x=q.front();q.pop; vis[x]=0; for(int i=head[x];i;i=edge[i].next) { int y=edge[i].to,z=edge[i].dis; if(dis[y]>dis[x]+z) { dis[y]=dis[x]+z; if(!vis[y]) q.push(y); } } } } ``` 本算法的优缺点： -
优点：一般情况下跑的比
Dijkstra 还快 -
缺点：出格子图可以直接卡掉。