一篇迟到了三个多星期的博客

前言

咳咳……

现在，Payphone−X 终于学完了最短路 （其实三周前就已经学完了的个说）

现在，他要胡扯一篇最短路总结

定义篇

可以先看看维基百科对于最短路的解释

最短路问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
—— 维基百科

是不是听起来很像废话……

还是来看看通俗一点的解释吧

最短路算法，即在一个加权图中求某两点相距的最短路程的长度的算法。

分为单源最短路与多元最短路两种。

其中

  • 多源最短路求的是图中所有点之间的最短路。

  • 单源最短路求的是图中任意一点到其他点之间的最短路。

松弛操作

在讲松弛操作之前，我们要先明确一个事实

那就是在计算两点间的最短路时，通常不仅仅会算出两点间的最短路，而会把许多点之间的最短路一同算出来

那……

这是为什么呐？？？

就是为了松弛操作。

松弛操作，从字面上解释就是指将两点间较长的路径进行替换，换为一条较短的路径。

换句话说，就是当你发现这两个地方之间还有更短的路可以走时，用这条路径来替换已知的较短路径，直到不能替换为止。

这时的 “已知的较短路径”，就是我们要求解的最短路。

松弛操作的基本模式是这样的

  • 对于任意两点 u，v 目前的最短路，我们可以用 u，w 与 w，v 之间的最短路去更新 u，v 的最短路，即s(u,v)=min(s(u,v),s(u,w)+s(w,v))

  • 在计算单源最短路时，若 u，v 目前的最短路为 s(u,v)， 则对于 v 所直接连到的节点 w，有s(u,v)=min(s(u,v),s(u,w)+s(w,v))

至于为什么这样做，原因还是在于单源 —— 因为我们在计算单源最短路时，只关心 u 到其他点的最短路，因此 w 到 v 的最短路就极不易求。因此，我们换为两点间的直接距离来减小时间复杂度。

这就是我们为什么要计算其他点最短路 —— 为了松弛操作的顺利进行。

Floyd-Warshall

三层循环，意味着邻接矩阵可行。
——Wei_taming

众所周知，Floyd 算法是一种极其简单的算法

但同时，它也是最快的多元最短路算法

Floyd 算法基于 DP，说白了，就是枚举中间点，不停地进行松弛操作来更新最短路。

代码实现也很容易，但时间复杂度比较高，为 O(n3)

模板如下

cpp
/*---Floyd---*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

int map[1001][1001];

int main(){
	int n;
	int a , b , c;
	memset(map , 0x3f , sizeof(map));
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a >> b >> c;
		map[a][b] = c ;
	}
	for(int k = 1; k <= n; k ++){
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= n; j ++){
				map[i][j] = min(map[i][j] , map[i][k] + map[k][j]);
			}
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++){
			cout << map[i][j] << " ";
		}
	}
	return 0;
}
//Written By Payphone-X

Dijkstra

众所周知，Dijkstra 是一种单源最短路算法，可以用于没有负边权的最短路问题。

而且 Dijkstra 基于贪心，相对来说比较好想一些。

它的实现流程如下：

  1. 选一个点做起始点。

  2. 遍历与起始点相连的所有边，寻找出一条最短的记录下来。

  3. 把这条边的另一个端点作为起始点，然后循环。

举个栗砸

就像下图（点不开的请自觉滚回长城里边）

EYx2z4.gif

EYx2z4.gif

markdown
第一次循环，发现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进行松弛操作：

正因如此，Dijkstra 的时间复杂度较高，为 O(n2)

但 Dijkstra 的算法稳定性比较强，也就是说，Dijkstra 很难被卡。

而且不难看出我们在 dis 数组中选择最小值时，可以用一些数据结构来进行优化。线段树？平衡树？

下面，我们就来研究一下这些优化。

Dijkstra + priority_queue

  • 不难发现，当我们在 dis 数组中寻找最小值时，需要一个个进行遍历。

  • 因此，我们可以将其放入优先队列（堆）中，直接弹出。

  • 优化后的时间复杂度为 O(nlogn)

模板如下

cpp
/*---Dijkstra + Heap---*/
#include<iostream> 
#include<algorithm>
#include<climits>
#include<queue>
#include<cstring>
#include<cstdio>

using namespace std;

struct Edge{
	int to;
	int last;
	int dis;
}edge[500001];

int edge_number;
int end[500001];

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 dis[500001];
int n;
bool vis[500001];

inline void Dijkstra(int s){
	priority_queue< pair<int , int> , vector<pair<int , int> > , greater<pair <int , int> > > Q;
	for(int i = 1; i <= n; i ++){
		if (i != s){
			dis[i] = 0x3f3f3f3f;
		} 
	}
	for (int i = 1; i <= n; ++i) Q.push(make_pair(dis[i], i));
	while(!Q.empty()){
		int v = Q.top().second;
		Q.pop();
		if(vis[v] == true){
			continue;
		} 
		vis[v] = true;
		for(int i = end[v]; i != 0;i = edge[i].last){
			int to = edge[i].to;
			if(dis[to] > dis[v] + edge[i].dis){
				dis[to] = dis[v] + edge[i].dis; 
				Q.push(make_pair(dis[to],to));
			}
		}
	}
}

int main(){
	int m , s;
	int a , b , c; 
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i ++){
		cin >> a >> b  >> c;
		add_edge(a , b , c);
	}
	Dijkstra(s);
	for(int i = 1; i <= n; i ++){
		cout << dis[i] << " ";
	}
	return 0;
}
//Written By Payphone-X

SPFA

SPFA 与 Dijkstra 一样，是一种单源最短路算法

而且……

SPFA 可以处理负边权

那么

为什么 SPFA 可以处理负边权呐？？？

众所周知，SPFA 是一个基于队列的算法，它的实现流程大概是这样的

  1. 初始化 dis 数组，将其全部赋值为一个很大的数

  2. 选一个点做起始点，并将起始点丢入队列。

  3. 改变所有与起始点相连点的最短路，并做出标记

  4. 弹出起始点，把刚刚标记的所有点作为起始点丢进队列，并循环，直到队列为空为止。

还不懂？

举个栗砸

就像下图，我们以点 a 为起始点

EtKaSH.jpg

EtKaSH.jpg

首先我们建立从点 a 到各点的最短路数组，建出来后就像这样。

EtK6k8.jpg

EtK6k8.jpg

然后我们把起始点 a 放入队列，对以 a 为起始点的所有边进行松弛操作，并更新最短路。完成后表格如下

EtMl9g.jpg

EtMl9g.jpg

在松弛时三个点的最短路径变小了，而这些点队列中都没有出现，因此这些点需要入队。此时，队列中新入队了三个结点 b,c,d

之后节点 b 出队，把以 b 为起始点的所有边进行松弛操作，并更新最短路。完成后表格变成了这个样子

EtMDgJ.jpg

EtMDgJ.jpg

现在 e 点的最短路径也已经改变，因此，我们把它也扔进队列中。依次循环……

以下省略 3000 字……

最后，我们算出了所有点的最短路。表格如下

EtMIvd.jpg

EtMIvd.jpg

是不是很简单吖（逃

由此可以看出，SPFA 在面对负边权时，不会像 Dijkstra 一样进行无脑循环，而是加入队列。

因此，SPFA 是可以处理负边权的。但 SPFA 不能处理负权回路

时间复杂度为 O(km)， 其中，m 为边数，而 k 为每个节点的平均入队次数，一般为 2。至于为啥我也不会证

模板如下

cpp
/*---SPFA---*/
#include<iostream>
#include<algorithm>
#include<queue>

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;
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(s);
    visited[s] = true;
    int first;
    while(!Q.empty()){
        first = Q.front();
        Q.pop();
        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;
                if(visited[edge[i].to] == false){
                    visited[edge[i].to] = true;
                    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

SPFA 的算法优化

由于 SPFA 过于优秀太容易卡，因此 SPFA 有许多算法优化。

可以帮死去的 SPFA 做心肺复苏

下面，我们就来具体看一下 SPFA 的优化

SLF（Small Label First）

SLF 的思路其实很简单：

我们把朴素算法下 SPFA 的队列改为双端队列（即 deque）。

对于每一个加入队列的节点 s，如果 dis[s] < 队首的 dis[first]， 则 u 被加入队首。

否则的话，u 被加入队尾。

模板如下：

cpp
/*---SPFA + SLF---*/
#include<iostream>
#include<algorithm>
#include<queue>


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 的平均值为止。

模板如下：

cpp
/*---SPFA + LLL---*/
#include<iostream>
#include<queue>

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

不多说，直接上代码

模板如下

cpp
/*---SPFA + SLF + LLL---*/ 
#include<iostream>
#include<queue>

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 时出题人讲评时的照片）

ENfx8P.jpg

ENfx8P.jpg

或者说，你们可以看一下某乎上的一篇文章

作者在这篇文章里找到了一位用户的回答：

SPFA 的受到怀疑和最终消亡，是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。
—— 一位知乎用户

作者不对这位用户做出任何评价，因为作者也没有这个资格。

但作者认为，如果一昧的在存在负边权的图中丧心病狂的卡 SPFA，也没有什么意思。

参考资料

  1. Herself32’s Github Blog

  2. Sshwy’s Blog

  3. 洛谷日报第 111 期 - SPFA 算法的玄学方法

  4. muximuxi525’s 博客园

鸣谢上面的几位 dalao 在最短路方面给予我的帮助

更新日志

  • 2019.5.2 更新了 SPFA， SPFA + SLF 代码，并修改少量错别字。

  • 2019.5.3 更新了 SPFA + LLL， SPFA + SLF + LLL 代码，卡 SPFA， 参考资料部分.

THE END