简单的图论（拓扑排序 & Dijkstra & SPFA & Bellman-ford & Floyd） 笔记

项目	拓扑排序	Dijkstra	SPFA	Bellman ford	Floyd
时间复杂度	$O(V+E)$	$O(\log V\times E)$	$O(VE)$	$O(VE)$	$O(V^3)$
空间复杂度	$O(V)$	$O(V)$	$O(V)$	$O(V)$	$O(V^2)$
源	$\text{单}$	$\text{单}$	$\text{单}$	$\text{单}$	$\text{多}$
判断图是否存在环（边权不为负）	$\text{Yes}$	$\text{No}$	$\text{No}$	$\text{No}$	$\text{No}$
是否支持负边	$\text{No}$	$\text{No}$	$\text{Yes}$	$\text{Yes}$	$\text{Yes}$
判断图是否存在负环	$\text{No}$	$\text{No}$	$\text{Yes}$	$\text{Yes}$	$\text{No}$
是否支持限制通过的边数	$\text{No}$	$\text{No}$	$\text{No}$	$\text{Yes}$	$\text{No}$

---

一、拓扑排序

1. 用途

基本概念：在一个有向无环（DAG）图中，用一条起点为 $u$，终点为 $v$ 的有向边表示工程 $u$ 必须在工程 $v$ 之前执行，那么就将这种图称为 AOV 网。

拓扑序列：若由这个有向图每个顶点的编号组成的序列，满足下面的几个条件，那么就称这个序列是这个有向图的拓扑序列。

• 每个顶点出现且只出现一次。

• 若工程 $x$ 需在工程 $y$ 之前执行，则 $x$ 必须比 $y$ 先出现。

2. 实现方法

(1). 建图

五种算法除了 Bellman-Ford 和 Floyd 以外，均使用链式前向星存储图。

(2). 排序

首先用一个队列来存储当前需要处理的点的编号，用一个数组来存储每个数组的入度（在输入的时候，每输入一条边，该边的终点的入度就加 $1$）。

先把入度为 $0$ 的点全部加入到队列当中，遍历这些点所连的边，将它们的入度减 $1$（因为它们与这个入度为 $0$ 的点的边被删去了），同时判断是否存在入度为 $0$ 的点，存在就把这个点也加入到队列之中等待处理。

需要注意的是，当图中还有顶点未被处理时，已经找不到了入度为 $0$ 的点，说明这个图由环，如下图所示：

图炸了

这时，$2$ 要在 $1$ 之前完成，$3$ 要在 $2$ 之前完成，$4$ 要在 $3$ 之前完成，而 $1$ 又要在 $4$ 之前完成，产生了矛盾，因此，这个图不存在拓扑序列。

3. 模板题代码

平台	网址
洛谷	https://www.luogu.com.cn/problem/B3644

拓扑排序部分代码如下：

bool topsort(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(!idg[i])q.push(i);//将入度为 0 的点放入队列
	}
	while(!q.empty()){
		int t=q.front();
		top[++cnt]=t;//存储拓扑序
		q.pop();
		for(int i=head[t];i;i=edge[i].next){
			int j=edge[i].v;
			if(!(--idg[j]))q.push(j);//寻找其它入度为 0 的点
		}
	}
	if(cnt<n)return false;//如果拓扑序的长度与原数列长度不符，说明存在环
	return true;
}

---

二、Dijkstra

1. 用途 & 优势

从此往后的四种算法，都是用来解决一个点到另一个点的最短路径的问题的。但是四种算法在使用上又有略微的不同，具体可看文章顶部表格。

Dijkstra 的优势是它优秀的时间复杂度，仅为 $O(\log V\times E)$，只要数据中不存在负边，Dijsktra 在这四种算法中一般都是最优的。

2. 实现方法

• 定义一个为小根堆的优先队列，优先队列的类型为 pair <int, int> 类型，此时，队列按 pair 的第一个数从小到大排序，将待处理点离起点的距离与该点的编号存入优先队列中。用 $di{s}_i$ 来表示点 $i$ 到起点 $v_0$ 的距离

• 初始化，将起点 $di{s}_{v_0}$ 赋值为 $0$，将其他每一个 $di{s}_i$ 赋值为 $inf$，并将 $di{s}_{v_0}$ 与 $v_0$ 存入优先队列中。

• 取出队列头部的元素 $v_j$，若 $v_j$ 已经被访问过，则舍弃 $v_j$ 继续取出接下来队列头部的元素。否则标记该点已被访问过。

• 按距离从短到长遍历每个与 $v_j$ 相连的节点 $v_k$，松弛从 $v_0$ 到 $v_k$ 的距离，比较方法为看是从 $v_0$ 直接前往 $v_k$ 的距离更短，还是从 $v_0$ 经 $v_j$ 到 $v_k$ 的时间更短。若用 $len$ 表示 $v_j$ 到 $v_k$ 的距离，则：

$$di{s}_{v_k}=min(di{s}_{v_k},di{s}_{v_j}+len)$$

3. 模板题代码

平台	网址
洛谷	https://www.luogu.com.cn/problem/P3371

Dijkstra 部分代码如下：

void dij(int x){
	dis[x]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	q.push({0,x});
	while(!q.empty()){
		pair<int,int> t=q.top();
		q.pop();
		int u=t.second,dist=t.first;
		if(b[u])continue;
		b[u]=true;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v;
			if(dis[v]>dist+edge[i].len){
				dis[v]=dist+edge[i].len;//松弛操作
				q.push({dis[v],v});
			}
		}
	}
}

---

三、SPFA

1. 优势

SPFA 可以以一个较低的时间复杂度达到处理负边和判断负环的效果。在大多数情况下，SPFA 的时间复杂度只有 $O(\alpha V)$，其中 $\alpha$ 只为一个常数。只有在少数情况，如图为一个网格图的时候，SPFA 才会退化为 $O(VE)$ 的时间复杂度。

2. 实现方法

将起点加入队列，利用松弛将与这个点所有相连的边的距离更新一次，如有更新成功的，并且其不在待处理的点的队列中，就将这个更新成功的点也加入队列。

此外，可以用一个数组 $id{g}_i$ 来记录点 $i$ 已经被更新的次数，若不存在负环，这个值即位 $i$ 的入度，否则，若有一个点的入度已经比整个图的点数还要多了，说明存在一个负环使得这一段路径被循环执行，此时可以退出 SPFA，返回存在负环的结果。

3. 模板题代码

题目1. 求最短路：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。数据保证不存在负权回路。1≤n,m≤100000 ,图中涉及边长绝对值均不超过 10000。

SPFA 部分代码如下：

bool spfa(int s){
	fill(dis,dis+N,oo);
	queue<int> q;
	vis[s]=true;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		vis[t]=false;
		for(int i=head[t];i;i=edge[i].next){
			int v=edge[i].v;
			int w=edge[i].len;
			if(dis[v]>dis[t]+w){
				dis[v]=dis[t]+w;
				if(!vis[v]){//如果这个点当前不在队列中，将其加入至待处理的队列内
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
}

题目2. 判断负环：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你判断图中是否存在负权回路。1≤n≤2000 ，1≤m≤100000，图中涉及边长绝对值均不超过 10000。

松弛时通过入度数量判断负环的部分如下：

if(dis[v]>dis[t]+w){
	dis[v]=dis[t]+w;
	if(!vis[v]){
		q.push(v);
		vis[v]=true;
		if(++idg[v]>n)return false;//如果点 v 的入度已经大于总点数，返回不存在最短路径。
	}
}

---

四、Bellman-ford

1. 优势

Bellman-ford 在单源最短路径中几乎可以说是全能。存负边，判断负环，甚至可以限制松弛的步数。并且时间复杂度也不算特别差，与 SPFA 相同，为 $O(VE)$。

2. 实现方法

(1). 建图

Bellman-ford 有独特的建图方式：对于编号为 $i$ 的边 $e$，它被存储在结构体 $edg{e}_i$ 当中，其中，$e_u$ 表示边 $e$ 的起点，$e_v$ 表示边 $e$ 的终点，$e_w$ 表示边e的权值。存图与建图的代码如下所示：

struct EDGE{
	int u,v,len;
}edge[N];
//输入时直接存储
for(int i=1;i<=m;i++){
	cin>>edge[i].u>>edge[i].v>>edge[i].len;
}

(2). 松弛

由于最短路最多经过 $n-1$ 个节点就能得到，所以对所有边松弛 $n-1$ 轮。

每轮时，遍历存储的每一条边，比较该边的终点是否能被该边的起点松弛。

如果进行了 $n-1$ 轮松弛之后，仍有边能够被松弛，说明图存在负环。

如果需要限制通过 $k$ 条边，只需要将松弛 $n-1$ 次改为松弛 $k$ 次即可，通过 $k$ 条边，则相当于最多经过 $k$ 个顶点，所以对所有边松弛 $k$ 轮。

3. 模板题代码

题目1：求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边但不存在自环， 边权可能为负数。请你求出从 1 号点到 n 号点最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。1≤n≤500 ，1≤m≤10000，任意边长的绝对值不超过 10000。

Bellman-ford 部分的代码如下：

void bellman(int x){
	dis[x]=0;
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m;j++){
			int u=edge[j].u;
			int v=edge[j].v;
			int w=edge[j].len;
			if(dis[u]!=oo and dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
			}
		}
	}
}

题目2：判断负环

给定一个 n 个点 m 条边的有向图，边权可能为负数。请判断该图是否存在负环，如果存在输出“Yes”,否则输出“No”。1≤n≤500 ，1≤m≤10000，任意边长的绝对值不超过 10000。

最后判断负环的部分如下：

for(int i=1;i<=m;i++){
	int u=edge[i].u,v=edge[i].v;
	if(dis[u]==oo or dis[v]==oo)continue;//这条边所连的点无法到达 
	if(dis[u]+edge[i].len<dis[v])return false;//还能继续松弛，存在负环 
}
return true;

题目3：限制通过边数

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。注意：图中可能 存在负权回路 。1≤n,k≤500 ，1≤m≤10000，任意边长的绝对值不超过 10000。

Bellman-ford 部分的代码如下

void bellman(int x){
	dis[x]=0;
	for(int i=1;i<=k;i++){
		memcpy(last,dis,sizeof dis);//将当前距离复制一份，防止一次循环多次操作导致无法限制通过的边数
		for(int j=1;j<=m;j++){
			int u=edge[j].u;
			int v=edge[j].v;
			int w=edge[j].len;
			if(dis[u]!=oo and dis[v]>last[u]+w){
				dis[v]=last[u]+w;
			}
		}
	}
}

五、Floyd

1. 优势

Floyd 唯一的优势，就是它能够求多源最短路径，即一张图中任意一个点为起点到达其他点的最短路径，不过这也牺牲了大量的时间复杂度与空间复杂度，分别达到了 $O(V^3)$ 与 $O(V^2)$。

2. 实现方法

(1). 建图

Floyd 使用邻接矩阵来建图，这也是它空间复杂度爆炸的原因之一。用 $f_{i,j}$ 来表示 $i$ 与 $j$ 之间的最短路径。初始化时，$f_{i,j}\leftarrow inf,i\ne j$。存储时，输入的数据直接按照上述所说存入 $f$ 中，代码如下所示：

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		if(i!=j)f[i][j]=oo;
	}
}
for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	f[u][v]=min(f[u][v],w);//两点之间的距离，长度取最小
}

(2). 松弛

Floyd 的松弛方法，是枚举每一个 $i$ 与 $j$，并为 $i$ 与 $j$ 枚举松弛的中间点 $mid$，判断是当前直接从 $i$ 前往 $j$ 近，还是从 $i$ 经 $mid$ 到 $j$ 近，状态转移方程如下：

$$f_{i,j}=min(f_{i,j},f_{i,mid}+f_{mid,j})$$

3. 模板题代码

题目1：求多源最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。数据保证图中不存在负权回路。1≤n≤200 ，1≤k≤n，1≤m≤20000。图中涉及边长绝对值均不超过 10000。

Floyd 部分代码如下：

void floyd(){
	for(int mid=1;mid<=n;mid++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][mid]+f[mid][j]);
			}
		}
	}
}