摘要
复习一下模板
2019.6.4：编入精选文章
图的最短路，指的是在一个加权图 G 中某两点相距的最短路程的长度（有时要求记录路径）。
严格地说，最短路分有向与无向两种。有向的最短路强调起点和终点的区别，而无向的最短路则只需要连接两点的边的路径权值和最小就行了。
单源与多源最短路
计算最短路，通常不会只求某两点的最短路，而会将许多点对间的最短路一起算出来。这具体表现在：
- 单源最短路：计算图 G 中某一点 s 到其他的所有点的最短路
- 多源最短路：计算图 G 中任意两点的最短路
至于为什么会计算出其他点的最短路，下文将揭晓
松弛操作
最短路算法，都会运用到松弛操作，字面义就是，将两点间原本的较长的最短路进行更新替换，松弛为较短的路径
也就是说，将当前存储的最短路长度进行更新，在算出其他点对间的目前最短路长度后，利用这个已知数据去更新与它直接连接到的结点，直到不能更新为止，此时的 “目前最短路” 即为最终要求的最短路。
松弛操作的基本模式是这样的：
- 对于两点 u，w 的目前最短路，利用 u，v 的目前最短路，v，w 的目前最短路去更新 u，v 的最短路，即
- 在单源最短路程序实现中，若已求得图 G 中两结点 u，v 的目前最短路为 s(u,v), 则对于 v 所直接连接到的结点 w:
至于为什么这么实现，原因在于单源——毕竟只关心 u 到其他点的最短路，那么 v 到 w 的最短路就极不容易求，因此替换为两点的直接距离，减小复杂度。
这就是为什么会计算出其他点的最短路的原因——为了松弛操作的更新。
注意事项
- 图 G 既可能是有向图，也有可能是无向图（可把无向图理解为双向连边切权值相等的有向图）；既可有环也可无环
- 勿把
u 到 v 的最短路和v 到 u 的最短路混为一谈，因为边是有向的，不一定能反着走 - 对于点对间的最短路长度的初始化，绝大多数情况会初始化为一个很大很大的数，方便更新
- 对于最短路的路径问题，通常是记录前一个结点的编号，即，在更新最短路长度的同时，更新结点编号
Dijkstra 算法
单源最短路算法，时间复杂度 ，利用二叉堆可优化到 。
算法描述
在图 G 中，s 为源结点。
定义 d[i] 为结点 s 到结点 i 的最短路，将 d[i] 初始化为很大的数，d[s] 初始化为 0（源点本身）。
定义 w(u,v) 为 u 到 v 直接连接的边的权值（保证 u 到 v 有直接连接的边，有方向性）。
定义 v[i] 记录结点 i 是否被访问，全部初始化为未访问；如果被访问，也代表最短路已经求得。
只要有结点未被标记：
- 找到目前还未被访问的 d[i] 中的最小值 d[p]，这是求出的 s 到 p 的最终的最短路。将 p 标记为已访问。
- 利用这个信息，对于与 p 连接的所有结点 q，进行 s 到 q 的松弛操作：
d[q]=min(d[q],d[p]+w(p,q)) - 重复上两个步骤，直到所有结点都被访问。
例如，以结点 1 为源点。
第一次，发现 d[1]==0 为最小值，于是标记结点 1 为已访问，对 2，3，5 进行松弛操作：
第二次，发现 d[2]==4 为最小值，于是标记结点 2 为已访问，对 1，3 进行松弛操作：
第三次，发现 d[3]==5 为最小值，于是标记结点 3 为已访问，对 1，2，4 进行松弛操作：
第四次，发现 d[5]==6 为最小值，于是标记结点 5 为已访问，对 1，4，6 进行松弛操作：
第五次，发现 d[4]==7 为最小值，于是标记结点 4 为已访问，对 3，5，7，8 进行松弛操作：
第六次，发现 d[8]==13 为最小值，于是标记结点 8 为已访问，对 4，7 进行松弛操作：
第七次，发现 d[6]==14 为最小值，于是标记结点 6 为已访问，对 5，7 进行松弛操作：
第八次，发现 d[7]==15 为最小值，于是标记结点 7 为已访问，对 4，6，8 进行松弛操作：
一点注解
至于为什么，每次要标记最小的结点，是因为：
- 你会发现，每次取到的最小值按序排列，是逐渐递增的（如例图中第 1 至 8 次找出的 0，4，5，6，7，13，14，15），换句话说，每次算出的目前最短路长度，是逐渐变长的。
- 再者，每次你计算的最小值，其实都是之前松弛操作更新后的结点（有红色数字的结点），不会遇到被初始化为 INF 的结点，因为每一次对该结点的遍历都会更新它所有相邻结点的目前最短路，为下一个最小结点做准备。
- 第三，假设所有被访问过的结点都求得最优解，用数学归纳法，则下一个最小结点，已经被与之相邻的已访问的结点松弛过；而未被访问的结点的值都大于等于这个结点，说明不可能从未被访问的结点松弛到这个结点；因此这个被与之相邻的已访问的结点松弛过的最小结点的
d[]，即为它最终的最短路的长度。从而，一步一步，算出全图的单源最短路。
Dijkstra - 堆优化
上述算法的复杂度为 ，遇到较大的数据将超时。在寻找每次的最小值时，可使用堆优化。每次取出的堆首的元素一定是已经求得最优解的。复杂度降到 .
我也不知道为什么这么点内容我能扯这么久
模板代码
const int N=1e5+5,M=2e5+5;
struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
int dist[N];
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
dist[s]=0,q.push(make_pair(0,s));
while(q.size()){
pii u=q.top();q.pop();
if(dist[u.second]<u.first)continue;
for(int i=h[u.second];i;i=e[i].nex){
const int &v=e[i].t,&w=e[i].v;
if(dist[v]<=dist[u.second]+w)continue;
dist[v]=dist[u.second]+w;
q.push(make_pair(dist[v],v));
}
}
}
SPFA 算法
SPFA 算法是 Bellman-Ford 算法的优化，全称为 Shortest Path Faster Algorithm.
有人问 Bellman-Ford 算法是是啥。其实这是 SPFA 的弱化版，反正你知道它大概可以被遗忘就对了
SPFA 算法的思想就是不断更新结点的状态，直到不能更新为止。而 SPFA 把待更新（待松弛）的结点存到队列中。
算法描述
在图 G 中，s 为源结点
定义队列 que 记录还需要进行松弛操作的结点； 记录结点 i 是否在队列中。
将源结点入队，并标记 .
当队列非空，即仍有结点需要松弛操作时，做下述操作：
取出队首为 ，标记 为出队。
对于结点 p 的所有正向连接结点做松弛操作 。
如果成功松弛（即 时）此时 q 结点的最短路被更新，则从 q 连出的所有最短路也应当更新。所以如果 q 已在队列中，就不用入队；否则，将 q 入队，标记 为入队。
队列空了，说明没有结点需要松弛，算法结束。
时间复杂度 。E 表示边数，k 为不定系数，通常为 2-3.
模板代码
struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt=0;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
int dis[N];
bool vis[N];
void spfa(){
memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(s), dis[s]=0;
while(q.size()){
int u=q.front();
q.pop(), vis[u]=0;
for(int i=h[u];i;i=e[i].nex){
const int &v=e[i].t, &w=e[i].v;
if(dis[v]<=dis[u]+c)continue;
dis[v]=dis[u]+c;
if(!vis[v])q.push(v), vis[v]=1;
}
}
}
SLF 与 LLL 优化
上述 SPFA 算法插入队列的决策是直接插入队尾，这样的时间复杂度仍有冗余。
Small Label First 策略，设要加入的结点是 j，队首元素为 i，若 d[j]<d[i]，则将 j 插入队首， 否则插入队尾。
Large Label Last 策略，设队首元素为 i，队列中所有 dist 值的平均值为 x，若 dist[i]>x 则将 i 插入 到队尾，查找下一元素，直到找到某一 i 使得 ，则将 i 出对进行松弛操作。引用网上资料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。
所以，SPFA 做为一个不稳定的算法，惨遭各种最短路模板卡，到底有什么用？
SPFA 可以处理带负权边的最短路，相比之下 Dijkstra 就不行，因为带负权的图无法保证每次遍历到的点是已求得最优解。差分约束也常用 SPFA 求解。
最短路与 DP
其实很多人可能会想到，我在取出堆首元素的时侯，其实可以判断该结点能否更新。如果不能更新，就用它更新它的相邻结点；否则就更新，然后重新丢到堆里面，等待下一次被取出。
如何判断能否更新？因为堆的键值就是最短路值，那么我们比较这个键值与 dist 数组就可以判断该结点是否被松弛过，如果未被松弛过就拿他更新别的结点。
这样的复杂度仍是 的。但是你发现它是可以用来处理带负权边的图的！
其实如果把 SPFA 改成用堆维护的话，你发现它 TM 也是这个算法！
两者最终都回归到了堆维护最短路的算法上。这实际上就是一种动态规划，而且带有一点迭代的性质在里面。动态规划通过 1 次或者若干次选择决策更新最优解的方式求解问题，而最短路算法的实质也是不断选择合适的边做为最短路上的边，以此更新当前结点的 DP 值。DP 的边界就是所有的结点都无法更新的时侯，这与迭代的边界类似。下午讲解的 Floyd 算法也是基于 DP 思想的多源最短路算法。
Floyd 算法
Floyd 用于求多源最短路径，即每两点的最短距离。
Floyd 基于动规，定义 表示从结点 i 到结点 j，经过（不包括起点终点）前 k 个结点的最短路
.
实际中可以把第一维直接压掉
时间复杂度 .
模板？只有两行 emmm 于是来一道模板题吧
[LG2910] 寻宝之路
给一个图，问顺次经过 的最短路长度。.
#include<iostream>
#include<cstdio>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int n,m,sum,a[10002],d[102][102];
int main(){cin>>n>>m;
FOR(i,1,m)cin>>a[i];
FOR(i,1,n)FOR(j,1,n)cin>>d[i][j];
a[0]=1,a[m+1]=n;
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)//floyd
if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];
FOR(i,0,m)sum+=d[a[i]][a[i+1]];
cout<<sum;
return 0;
}
～完结撒花～
