一篇迟到了三个多星期的博客
前言
咳咳……
现在，$Payphone-X$终于学完了最短路 （其实三周前就已经学完了的个说）
现在，他要胡扯一篇最短路总结
定义篇
可以先看看维基百科对于最短路的解释
最短路问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
——维基百科
是不是听起来很像废话……
还是来看看通俗一点的解释吧
最短路算法，即在一个加权图中求某两点相距的最短路程的长度的算法。
分为单源最短路与多元最短路两种。
其中
多源最短路求的是图中所有点之间的最短路。
单源最短路求的是图中任意一点到其他点之间的最短路。
松弛操作
在讲松弛操作之前，我们要先明确一个事实
那就是在计算两点间的最短路时，通常不仅仅会算出两点间的最短路，而会把许多点之间的最短路一同算出来
那……
这是为什么呐？？？
就是为了松弛操作。
松弛操作，从字面上解释就是指将两点间较长的路径进行替换，换为一条较短的路径。
换句话说，就是当你发现这两个地方之间还有更短的路可以走时，用这条路径来替换已知的较短路径，直到不能替换为止。
这时的“已知的较短路径”，就是我们要求解的最短路。
松弛操作的基本模式是这样的
对于任意两点 $u$，$v$目前的最短路，我们可以用$u$，$w$与$w$，$v$之间的最短路去更新$u$，$v$的最短路，即
在计算单源最短路时，若$u$，$v$目前的最短路为$s(u,v)$， 则对于$v$所直接连到的节点$w$，有
至于为什么这样做，原因还是在于单源——因为我们在计算单源最短路时，只关心$u$到其他点的最短路，因此$w$到$v$的最短路就极不易求。因此，我们换为两点间的直接距离来减小时间复杂度。
这就是我们为什么要计算其他点最短路——为了松弛操作的顺利进行。
Floyd-Warshall
三层循环，意味着邻接矩阵可行。
——Wei_taming
众所周知，Floyd算法是一种极其简单的算法
但同时，它也是最快的多元最短路算法
Floyd算法基于DP，说白了，就是枚举中间点，不停地进行松弛操作来更新最短路。
代码实现也很容易，但时间复杂度比较高，为$O(n^3)$
模板如下
/*---Floyd---*/ |
Dijkstra
众所周知，Dijkstra是一种单源最短路算法，可以用于没有负边权的最短路问题。
而且Dijkstra基于贪心，相对来说比较好想一些。
它的实现流程如下：
选一个点做起始点。
遍历与起始点相连的所有边，寻找出一条最短的记录下来。
把这条边的另一个端点作为起始点，然后循环。
举个栗砸
就像下图（点不开的请自觉滚回长城里边）
第一次循环，发现d[1]=0为最小值，于是标记结点1为已访问，对2，3，5进行松弛操作： |
正因如此，Dijkstra的时间复杂度较高，为$O(n^2)$
但Dijkstra的算法稳定性比较强，也就是说，Dijkstra很难被卡。
而且不难看出我们在dis数组中选择最小值时，可以用一些数据结构来进行优化。线段树？平衡树？
下面，我们就来研究一下这些优化。
Dijkstra + priority_queue
不难发现，当我们在dis数组中寻找最小值时，需要一个个进行遍历。
因此，我们可以将其放入优先队列（堆）中，直接弹出。
优化后的时间复杂度为$O(nlogn)$
模板如下
/*---Dijkstra + Heap---*/ |
SPFA
SPFA与Dijkstra一样，是一种单源最短路算法
而且……
SPFA可以处理负边权
那么
为什么SPFA可以处理负边权呐？？？
众所周知，SPFA是一个基于队列的算法，它的实现流程大概是这样的
初始化dis数组，将其全部赋值为一个很大的数
选一个点做起始点，并将起始点丢入队列。
改变所有与起始点相连点的最短路，并做出标记
弹出起始点，把刚刚标记的所有点作为起始点丢进队列，并循环，直到队列为空为止。
还不懂？
举个栗砸
就像下图，我们以点$a$为起始点
首先我们建立从点$a$到各点的最短路数组，建出来后就像这样。
然后我们把起始点$a$放入队列，对以$a$为起始点的所有边进行松弛操作，并更新最短路。完成后表格如下
在松弛时三个点的最短路径变小了，而这些点队列中都没有出现，因此这些点需要入队.此时，队列中新入队了三个结点$b,c,d$
之后节点$b$出队，把以$b$为起始点的所有边进行松弛操作，并更新最短路。完成后表格变成了这个样子
现在$e$点的最短路径也已经改变，因此，我们把它也扔进队列中。依次循环……
以下省略3000字……
最后，我们算出了所有点的最短路。表格如下
是不是很简单吖（逃
由此可以看出，SPFA在面对负边权时，不会像Dijkstra一样进行无脑循环，而是加入队列。
因此，SPFA是可以处理负边权的。但SPFA不能处理负权回路
时间复杂度为$O(km)$， 其中，$m$为边数，而$k$为每个节点的平均入队次数，一般为2。至于为啥我也不会证
模板如下
/*---SPFA---*/ |
SPFA的算法优化
由于SPFA过于优秀太容易卡，因此SPFA有许多算法优化。
可以帮死去的SPFA做心肺复苏
下面，我们就来具体看一下SPFA的优化
SLF（Small Label First）
SLF的思路其实很简单：
我们把朴素算法下SPFA的队列改为双端队列（即deque）。
对于每一个加入队列的节点$s$，如果$dis[s]$ < 队首的$dis[first]$， 则$u$被加入队首。
否则的话，$u$被加入队尾。
模板如下：/*---SPFA + SLF---*/
using namespace std;
struct Edge{
int to;
int dis;
int last;
}edge[500001];
int end[500001];
int edge_number;
void add_edge(int from , int to , int dis){
edge[++edge_number].to = to;
edge[edge_number].dis = dis;
edge[edge_number].last = end[from];
end[from] = edge_number;
}
deque<int > Q;
int dis[500001];
bool visited[500001];
int n , m , s;
int a , b , c;
void SPFA(int s){
for(int i = 1;i <= n;i ++){
dis[i] = 0x3f3f3f;
}
dis[s] = 0;
Q.push_back(s);
visited[s] = true;
int first;
while(!Q.empty()){
first = Q.front();
Q.pop_front();
visited[first] = false;
for(int i = end[first]; i ; i = edge[i].last){
if(dis[edge[i].to] > dis[first] + edge[i].dis){
dis[edge[i].to] = dis[first] + edge[i].dis;
Q.front() = first;
if(visited[edge[i].to] == false){
visited[edge[i].to] = true;
if(dis[edge[i].to] < dis[Q.front()]){
Q.push_front(edge[i].to);
}
else{
Q.push_back(edge[i].to);
}
}
}
}
}
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i <= m; i ++){
cin >> a >> b >> c;
add_edge(a , b , c);
}
SPFA(s);
for(int i = 1; i <= n; i ++){
if(dis[i] == 0x3f3f3f){
cout << "2147483647" << " ";
}
else{
cout << dis[i] << " ";
}
}
return 0;
}
//Written By Payphone-X
LLL（Large Label Last）
LLL的思路也很简单。
对于每一个要入队的节点$s$，我们把$dis[s]$与$dis$的平均值比较。
若$dis[s]$更大，就把其放入队尾，再取队首元素进行比较。直到队首的$dis[s]$ < $dis$的平均值为止。
模板如下：/*---SPFA + LLL---*/
using namespace std;
struct Edge{
int to;
int dis;
int last;
}edge[500001];
int end[500001];
int edge_number;
void add_edge(int from , int to , int dis){
edge[++edge_number].to = to;
edge[edge_number].dis = dis;
edge[edge_number].last = end[from];
end[from] = edge_number;
}
queue<int > Q;
bool visited[500001];
int dis[500001];
int n , m , s;
int a , b , c;
void SPFA(int s){
int cnt = s , sum = 0;
for(int i = 1; i <= s; i ++){
dis[i] = 0x3f3f3f3f;
}
dis[s] = 0;
Q.push(s);
visited[s] = true;
int first;
while(!Q.empty()){
first = Q.front();
while(dis[first]*cnt > sum){
Q.pop();
Q.push(first);
first = Q.front();
}
Q.pop();
cnt--;
sum = sum - dis[first];
visited[first] = false;
for(int i = end[first]; i != 0; i = edge[i].last){
if(dis[edge[i].to] > dis[first] + edge[i].dis){
dis[edge[i].to] = dis[first] + edge[i].dis;
if(visited[edge[i].to] == false){
sum = sum + dis[edge[i].to];
cnt ++;
Q.push(edge[i].to);
}
}
}
}
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i <= m; i ++){
cin >> a >> b >> c;
add_edge(a , b , c);
}
SPFA(s);
for(int i = 1; i <= n; i ++){
if(dis[i] == 0x3f3f3f){
cout << "2147483647" << " ";
}
else{
cout << dis[i] << " ";
}
}
return 0;
}
//Written By Payphone-X
SLF + LLL
不多说，直接上代码
模板如下/*---SPFA + SLF + LLL---*/
using namespace std;
struct Edge{
int to;
int last;
int dis;
}edge[500001];
int end[500001];
int edge_number;
void add_edge(int from , int to , int dis){
edge[++edge_number].to = to;
edge[edge_number].dis = dis;
edge[edge_number].last = end[from];
end[from] = edge_number;
}
int visited[500001];
int dis[500001];
int n , m , s;
int a , b , c;
inline void SPFA(int s){
deque<int >Q;
int cnt = s , sum = 0;
for(int i = 1; i <= n; i ++){
dis[i] = 0x3f3f3f;
}
dis[s] = 0;
Q.push_back(s);
visited[s] = true;
int first;
while(!Q.empty()){
first = Q.front();
while(dis[first]*cnt > sum){
Q.pop_back();
Q.push_back(first);
first = Q.front();
}
Q.pop_front();
cnt--;
sum-= dis[first];
visited[first] = false;
for(int i = end[first]; i != 0 ; i = edge[i].last){
if(dis[edge[i].to] > dis[first] + edge[i].dis){
dis[edge[i].to] = dis[first] + edge[i].dis;
if(visited[edge[i].to] == false){
sum+=dis[edge[i].to];
cnt ++;
if(dis[edge[i].to] < dis[Q.front()]){
Q.push_front(edge[i].to);
}
else Q.push_back(edge[i].to);
}
}
}
}
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i <= m; i ++){
cin >> a >> b >> c;
add_edge(a , b , c);
}
SPFA(s);
for(int i = 1; i <= n; i ++){
if(dis[i] == 0x3f3f3f){
cout << "2147483647" << " ";
}
else{
cout << dis[i] << " ";
}
}
return 0;
}
//Written By Payphone-X
综合来说，在使用SLF优化时可以使SPFA的运行效率提升 15% ~ 20% ，而SLF + LLL可以使SPFA效率提高 50% 以上。
但还是能卡掉哒QAQ
卡SPFA
不知道你们有没有在luogu上看到这么一句话
关于SPFA， 它死了。
事情其实是这样的
在NOI 2018 Day1 T1归程 中，出题人卡了SPFA，导致使用SPFA求最短路的OIer们从$100-> 60$ , $Ag->Cu$.
很多选手，都因此没能与理想的大学签约……（下图为NOI 2018时出题人讲评时的照片）
或者说，你们可以看一下某乎上的一篇文章
作者在这篇文章里找到了一位用户的回答：
SPFA 的受到怀疑和最终消亡，是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。
——一位知乎用户
作者不对这位用户做出任何评价，因为作者也没有这个资格。
但作者认为，如果一昧的在存在负边权的图中丧心病狂的卡SPFA，也没有什么意思。
参考资料
鸣谢上面的几位dalao在最短路方面给予我的帮助
更新日志
2019.5.2 更新了SPFA， SPFA + SLF代码，并修改少量错别字。
2019.5.3 更新了SPFA + LLL， SPFA + SLF + LLL 代码，卡SPFA， 参考资料部分.
