博客转载

  • 图论 1：主要介绍了关于图的组成要素

  • 图论 2：图的特殊结构—树

  • 图论 3：图的遍历的理论基础

  • 图论 4：图的遍历的具体实现（ BFS , DFS ）

  • 图论 5：深度优先搜索 DFS（图的树的遍历的算法）

  • 图论 6：图的两种表示方法

  • 图论简述：讲的比本文更全面

忘了强烈建议看看前三篇博客，可以节省不少理解的时间，知识点直击重点

相关知识总结

n 阶图: n 个顶点的图

有限图：一个图的点集和边集都是有穷集的图。

零图：边集为空集的图

无向图：每条边都是无向边的图

有向图：每条边都是有向边的图

完全图：图中每对不同的顶点之间都恰连有一条边相连。n 个端点的完全图有 n 个端点以及n(n−1)/2条边

通路：顶点与其关联边的交替序列

回路：首尾相连的通路。

这里回路好像和离散数学里的概念不大一样，注意区分

自环：若一条边所关联的两个结点重合，则称此边为自环

度：一个顶点的度是指与该点相关联的边的条数，顶点 v 的度记作 deg(v)

注意：一个自环的端点度数为 2

孤立点：度都为 0 的点

叶（悬挂顶点）：度为 1 的点

入度：在有向图中，一个顶点 v 的入度是指与该边相关联的入边（即边的终点是 v ）

的条数，记作 deg+(v)

出度：在有向图中，一个顶点 v 的出度是指与该边相关联的出边（即边的始点是 v ）

的条数，记作 deg-(v)

疏松图&稠密图：是一个相对概念。点较少边较多的图示稠密图，反之则是疏松图。

一般而言，E*2 接近 V 的大概率是稠密图

定理一

即在任意图中，度数之和等于边数的 2 倍

推论：（1）在任意图中，度数为奇数的点必然有偶数个.

（2）在任意图中，只有两个奇度的点必定是相连的

定理二

即在有向图中，所有点入度之和等于出度之和

无向图是没有入度和出度的概念的

图的存储方式

还没那水平讲明白，详细讲解就先看看大佬的博客吧

图的结构比较复杂，任意两个顶点之间都可能存在关系，不能用简单的顺序存储结构来表示。

如果运用多重链表，即一个数据域多个指针域组成的结点表示图中的一个结点，则会造成大量的空间损失。

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。它用两个数组保存数据：一个数组存储途中顶点信息，一个二维数组存储图中边或者弧的信息

无向图

边连着的两个端点都可以互相串通，所以存入边的时候是两个方向同时存入

特点：（1）1 表示有边，0 表示无边

（2）顶点的度是行内数组之和

（3）求取顶点邻接点，将行内元素遍历即可

（4）二维数组是一个对称的数组

有向图

有向图有入度和出度区分，存边不再是两个方向同时存入，而是按照指定方向单方向存入

特点：（1）1 表示有边，0 表示无边

（2）各行之和是出度，各列之行是入度

一般存边都是每行每行的存所以如此，如果反过来存边那么上述规律恰好相反

（3）求取顶点邻接点，将行内元素遍历即可

（4）二维数组不再是一个对称的数组

带权有向图

若是带有权值，那么就把每个表示有边的1换为权值数，而无边的 0 换位无穷大（因为权值可能为任意数，包括 0 和负值）

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*以带权图为例，提前开一个足够的graph数组*/
void init(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if(j!=i)graph[i][j]=inf;
    }
}
//邻接矩阵加边操作 
void add(int u,int v,int w){
	graph[u][v]=w;//无向图加边两边都加不用说 
	graph[v][u]=w;//有向图根据条件确定 
}

signed main()
{
    init();
	int n;cin>>n;//边的个数
	for(int i=0;i<n;i++){
		int u,v,w;cin>>u,v,w;
		add(u,v,w);//加边
	}
	return 0;
}

优缺点

优点 缺点
易于理解/代码简短 复杂度高、对于稀疏图浪费高
对于确定边效率高 对于不确定边效率极低
易处理重边 比如想知道某个结点出发的所有边需要逐一判断

邻接表

引入：由于邻接矩阵消耗空间大，容易造成浪费。为了减小空间消耗采用动态分布内存的思想，不再定义数组长度

不再是通过矩阵记录相邻点的关系了了，而是一种动态数组和链表相结合的存储方法，指记录相连的两个点的关系：动态数组存储定点信息，链表存储从个点出发能到达的其他点

特点：（1）图中顶点用一个一维数组存储

（2）图中每个顶点 Vi 的所有邻接点构成一个线性表

竖列为一维数组，记录的是每一个结点。横向就是 vector 模仿的链表，记录的是同一个起点出发的路，第 i 个链表的第 j 个值存储的是从顶点i出发到顶点 list[j] 的边的情况。

邻接表一般存储有向带权图，其中出度表叫邻接表，而入度表就是逆邻接表

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*以带权图为例，要用到结构体啊*/
const int maxn=1005;//点的数量

struct node{//vector模拟链表,to和val一一对应 
	vector<int> val;//权值或是其他信息
	vector<int> to;//下一个结点 
}ver[maxn];//结构体数组ver相当于存链表的那个一维数组


//初始化
void init(){
	for(int i=0;i<maxn;i++)
	ver[i].to.clear();
} 

void add(int u,int v,int w){
	 ver[u].to.push_back(v);//存入对应的值 
	 ver[u].val.push_back(w); 
}

signed main()
{
    init();//邻接表和链式前向星表都需要初始化
	int n;cin>>n;//边的个数
	for(int i=0;i<n;i++){
		int u,v,w;
        cin>>u>>v>>w;
		add(u,v,w);//单向加边，双向边就反过来再加一次 
	}
	return 0;
}

优缺点

优点 缺点
易于理解/代码简短 对重边处理不当
内存占用率低 需要遍历所有的边。一般情况下使用邻接表存图是会存储重边的，不会做重边的判断
对不确定边效率高 对确定边的效率低
比如，要遍历从某点出发的所有边，不会遍历到不存在的 比如，我想知道从 a 到 b 的距离，只能遍历

邻接矩阵和邻接表对比

思路浑然发生了改变，准确的说是为了节省空间人们找到了一种新的高效存图方法，根据这一新的方法又产生了链式前向星

链式前向星

值得骄傲的是这是中国独创的一种较中和的方法

链式前向星表也是一维数组和链式组合结构，每个结点 i 都有一个链表，链表存储的是以 i 为起点的所有边的集合（邻接表存储的是从i出发的所有顶点的集合）

即这种存图方法是以边为基础。但是不再是用 vector 实现链表了，而是用一个动态数组记录但是再要存入权值时结构体还是要用的

注意：注意和邻接表不同，链式前向星在加边时是在原有的链表结构的头部插入这条边，这样使得每次插入的时间复杂度为 O(1) ，所以链表的边的顺序和读入顺序正好是逆序的

相当于正向存边逆向遍历

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*以带权图为例，要用到结构体*/
const int V=1005;//最大顶点数
const int E=5005;//最大边数  
int cnt;//寄存指针

struct node{
	int next;//指向下一条边的数组下标 
	int to;//表示这条边的另外一个顶点 
	int w;//边的长度,即权值 
};

node edge[E];//定义边集结构体
int head[V]//head表示的是顶点i的第一条边的数组下标,-1表示没有边了

//初始化
void init(){
	cnt=0;//只需要初始化顶点数组,否则就成了死循环了
	memset(head,-1,sizeof(head)); 
} 

void add(int u,int v,int w){
	cnt++;//将之前的head[u]存的第一条边变为新加边的下一条边 
	edge[cnt].next=head[u];//将新加边作为head[u]存的第一条边
	head[u]=cnt;
	edge[cnt].to=v;
	edge[cnt].w=w; 
}

//遍历从顶点k开始的所有的边 
void trav(int k){
	for(int i=head[k];i!=-1;i=edge[i].next)
	cout<<k<<"->"<<edge[i].to<<"w"<<edge[i].w<<endl;
}

signed main()
{
	init();//存边先初始化
	int n;cin>>n;//边的个数
	for(int i=0;i<n;i++){
		int u,v,w;
        cin>>u,v,w;
		add(u,v,w);add(v,u,w);//同上，无向图双向加边
	}
	int k;cin>>k;
	trv(k);//遍历以k为顶点的所有边
	return 0;
}

邻接表和链式前向星对比

总结

  • 对于邻接矩阵存图来说，由于内存消耗的局限性，它的适用范围比较狭窄，几乎只能在简单图论题目中见到

  • 邻接表是常见的一种存图方式，绝大部分采用 C++STL 中的 vector 实现，一般情况下大部分图论题目都能使用该存图方式

邻接矩阵与邻接表相比，疏松图多用邻接表，稠密图多用邻接矩阵

  • 链式前向星其实是一种较好替代邻接表来存图的数据结构，在邻接表存图不能使用时可以使用，几乎可以用于全部图论题目

推荐前期使用邻接矩阵入门，后期再使用链式前向星

图的遍历

邻接矩阵

看看这篇博客理论实现就好，代码写的太复杂了没必要看

BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*以无向带权图为例*/ 
const int inf=0x3f3f3f3f;//无穷大
const int maxn=1005;//顶点数

int g[maxn][maxn];//开的邻接矩阵表 
bool vis[maxn];//标记是否经过，初始化为0

//初始化
void init(){
	memset(vis,0,sizeof(vis));
	for(int i=0;i<maxn;i++){
		for(int j=0;j<maxn;j++){ 
			if(i==j)g[i][j]=0;
			else
			g[i][j]=inf;
		}
	}
}

//加边
void add(int u,int x,int w){
	g[u][v]=w;
	g[v][u]=w;
}

//bfs遍历，以u为起点
void bfs(int u){
	queue<int> q;
	q.push(u);//起点入队
	vis[u]=1;//标记为经过 
	while(!q.size()){//当队列不为空时 
		//取出队首元素
		int temp=q.front();
		q.pop();
		//遍历所有相邻的点
		for(int i=1;i<=n;i++){//对称矩阵，看横向的元素就好了 
			if(!vis[i]&&g[temp][i]!=inf){
				//...要进行的操作
				q.push(i);//入队
				vis[i]=1;//标记为经过 
			}
		} 
	} 
}

//需要遍历全图
void bfs(){
	for(int i=1;i<=n;i++){
		if(!vis[i]){//没有经过 
			bfs(i);
		}
	}
} 

signed main()
{
	init();
    int n;//存入的边数
	cin>>n;
	for(int i=0;i<n;i++){
		int u,v,w;cin>>u,v,w;
		add(u,c,w);
	}
	bfs();
	return 0;
}

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*无向图的DFS遍历，大题部分和上述BFS一样，主要看核心*/
const int inf=0x3f3f3f3f;//无穷大
const int maxn=1005;//顶点数

int g[maxn][maxn];//开的邻接矩阵表 
bool vis[maxn];//标记是否经过，初始化为0

//dfs遍历，以u为起点，depth为深度
void dfs(int u,int depth){
	vis[i]=1;//标记为经过
	for(int i=0;i<n;i++){
		if(!vis[i]&&g[u][i]!=inf){
			//...一系列操作
			dfs(i,depth);//以这个点为基础尝试后面，不行了再回来 
		}
	} 
} 

//遍历全图
void dfs_trav(){
	for(int i=1;i<=n;i++){
		if(!vis[i])
		dfs(i,1);
	}
}

链式前向星

BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*链式前向星表无向图的DFS遍历*/
const int maxn=1005;//顶点数
bool vis[maxn];

void bfs(int u){//以u为起点的bfs 
	queue<int> q;
	q.push(u);//起点入队
	vis[u]=1;//标记起点
	while(!q.empty()){
		//取出队首元素
		int temp=q.front();
		q.pop();
		vis[temp]=1; 
		for(int i=head[temp];i!=-1;i=edge[i].next){
			if(vis[edge[i].next])
			q.push(edge[i].to);
		}
	} 
}

void bfs_trav(){
	for(int i=1;i<=n;i++){ 
		if(!vis[i]) 
		bfs(i);
	} 
}

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*链式前向星表无向图的DFS遍历*/
void dfs(int x){
	vis[x]=true;
	//...一系列操作
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(!vis[edge[i].next])
		dfs(edge[i].to);
	} 
}

//遍历全图
void dfs_trav(int n){
	for(int i=1;i<=n;i++){
		if(!vis[i])
		dfs(i);
	}
}

图的最短路径问题

概念：简而言之就是找出两点之间权值最小的路径（权值一般代表长度嘛）

若是无向图其实让求最短路径的时候就是默认了两点之间的路径权值为 1

基本思想：无论什么算法，都是基于一个最基本的思想——松弛原理，即刷新最短路径

以上图为例，假如点 1 到点 2 的最短路是 2 ，点 2 到点 3 的最短路是 1 ，而图中点 1 直接到点 3 的距离是 6 ，那么，很明显点 1 到点 2 到点 3 比点 1 直接到点 3 短得多。那么，我们的最短路 dis[1][3] 就等于dis[1][2]+dis[2][3]。可以这么理解：点 1 到点 2 这条边的边权已经是点 1 到 2 点的最短路了，同样，点 2 到点 3 也是，那我们就可以用这两条最短路来刷新点 1 到点 3 的最短路，如果以后遇到更短的最短路方案再次刷新，这就是用最短路来松弛最短路了。

Floyd算法

原理：枚举每一个点作为中转点，然后利用动态规划的思想不断刷新每两点之间的最短距离。看似简单粗暴，实际上可以巧妙地缩小规模，无论有多少个中转点，我们都是从少到多往下推

适用问题：无负环的稠密图（边的条数|E|接近|V|²，称为稠密图）求多源最短路径问题的最优算法

特点：只要跑一遍Floyd算法，在其维护生成的 dis 二维数组里任意 dis[i][j] 就是顶点 i 到顶点 j 的最短路径（多源）

假设我们现在不允许有中转点，那么各个点之间的最短路应该是题目给出来的边权

现在我们只允许通过1号节点来进行转移，注意是1号而不是1个，因为我们现在考虑的是枚举的顺序，即怎么枚举。现在我们只需要枚举 i 和 j ，比较 dis[i][1]+dis[1][j]和 dis[i][j] 的大小，如果小于则刷新 dis 数组

接着，我们允许通过 1 号点和 2 号点进行转移，注意这里的“和”，一方面，2 号点本身可以独自松弛一些路径，另一方面，之前通过1号点松弛的一些路径中，可能有和2号点连着的。比如说，在上一轮我们用 dis[5][1]+dis[1][2] 松弛了 dis[5][2] ，然后我们再用这个路径去松弛其他路径，实际上就相当于通过1号点和2号点进行转移，所以我们的条件是“允许通过1号点和2号点”。不必考虑中转点的数量，用编号更大的点做中转点时，实际上也包含了编号小的中转点。所以，这里我们仍然只需要枚举 i 和 j ，用 dis[i][2]+dis[2][j] 去尝试松弛 dis[i][j] 就行了，这里的中转点我们可以用k来表示

依次类推到 k=n 的情况，即可以用 1~n 所有的点进行中转

实现：定义一个数组 f[k][x][y] ，表示只允许经过结点1到k，结点x到结点y的最短路径。很显然，f[n][x][y]就是x到y的最短路径。我们现在利用dp思想来更新求出这个数组：f[k][x][y]=min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y])

我们发现实际上一维数组没有用，直接改写为：f[x][y]=min(f[x][y],f[x][k]+f[k][y])

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Floyd(){
	//初始化dp数组
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		dp[i][j]=graph[i][j];//没有中转点,最短距离就是两点的边权 
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dp[i][j]>dp[i][k]+dp[k][j])
				dp[i][j]=dp[i][k]+dp[k][j];
			}
		}
	} 
}

优缺点

优点 缺点
易理解/代码短 时间复杂度太高了 O(n3)
跑一次任意两点间距离都出来了 一般顶点数超过 1000 个就 TLE 了

Dijkstra算法

引入：Floyd算法时间复杂度太高，只能处理顶点比较少的问题，如果顶点数太多又该怎么求最短路呢？

思考：Floyed 慢的原因是它无法保证当前求得的最短路一定是最终最优的（因为dp本来就是不断更新当前最优的过程），那我们能不能保证每次求得最短路是最优的呢？答案是可以的，但是需要舍弃一些东西

原理：BFS 思想+贪心思想

适用：无负权图求单源最短路径问题

特点：只适用于非负权图，但是时间复杂度非常优秀 O(n2) ，是用来求单源最短路径的算法

模板

这个板子利用了贪心求两点最小以达到所求两点间距离最小。但是循环时不会停止，也就是每一次尝试都是后面的点和遍历的点的距离都更新一次。 也就是说每次找一个最近点得花费不少时间

课件上有过程演示，想不明白了就去看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int maxn=1005;//顶点数
const int inf=0x3f3f3f3f;

int n;//记录顶点数
int dis[maxn];
int graph[maxn][maxn];
bool vis[maxn];

void init(){
	memset(vis,0,sizeof(vis));
	//graph初始化，这是必须的
	//...其他的初始化 
}

void dij(int start){//注意，start不一定是哪一个点 
	int x;//记录最近的未遍历点
	int minn;//临时保存当前的最短距离
	
    vis[start]=1; //标记起点
	//初始化dis,里面存入start到各点的距离
	for(int i=1;i<=n;i++)
	dis[i]=graph[start][i];
	
    //一次性求出从距离近的点到远的点距离start的最短路径
	for(int i=1;i<n;i++){//i==n的时候，到终点了就不需要再遍历了 
		minn=inf;//初始化minn为最大，其实minn就是用来找最近的未遍历的点 
		
        //遍历最小的dis[i]
        for(int j=1;j<=n;j++)
		if(!vis[j]&&dis[j]<minn){ 
			minn=dis[j];
			x=j;//x记录下来现在遍历了的点
		} 
		vis[x]=1;//标记已经遍历过的点
		
        //j就相当于y,遍历与x相邻的y的点，更新dis[j]的值
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]>dis[x]+graph[x][j])
			dis[j]=dis[x]+graph[x][j];
		} 
	} 
}

Dijkstra算法堆优化

引入：普通版本的dijkstra算法时间复杂度为 O(n2) ，而且是实打实的 O(n2) ，不会提前结束循环。如果顶点数超过10000 可能还是会爆时间。

最起码比 Floyd 好了一点了

思考：我们发现每次找一个最近点有点耗时，能不能加快寻找最近点的速度？我们发现好像前面讲的图的 bfs 遍历好像更适合实现dijkstra算法，但是我如何保证队列里面取出的元素就是队列里面最小的呢？

解决：我们已经学了神奇的STL，STL里面有个东西叫 priority_queue ，可以实现自动排序。说到 bfs 遍历和队列就又想到了链式前向星这个非常适合图遍历的数据结构，而链式前向星存的是某点出发的边集合，很适合求单源最短路的 dijkstra 算法，于是就诞生了——链式前向星实现优先堆优化的 Dijkstra

独特的优点：若是题目给出的两点的边有多条，其他的算法在存入的时候都需要和已存入的路做一下比较然后更新选择权值最低的边，而用此算法则不需要

原因：链式前向星不同于其他的存法，它是以边为基础存入，所以在整个更新的过程中它不得不将每一个存入的边用来更新 diskstra ，不管是重复的边还是没有重复的边

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//堆优化dijkstra
#include<bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
typedef pair<int,int> P;//用 P代替 pair<int,int>
//pair可以理解成一个讲两个变量捆绑起来的东西 

const int V=1e5+5;//最大顶点数
const int E=2e5+5;//最大边数

int dis[V],head[V];

struct node{
    int nex,to,w;
}edge[E];

int cnt;//寄存指针

void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
}

inline void add(int u,int v,int w){//内联函数加快速度 
    cnt++;
    edge[cnt].nex=head[u];
    head[u]=cnt;
	edge[cnt].to=v;
    edge[cnt].w=w;
}

void dij(int start){
    //初始化放在init()里也可以
    memset(dis,inf,sizeof(dis));
	
    //定义优先队列存 pair，小顶堆，注意最后两个尖括号间必须有空格。 
    priority_queue<P,vector<P>,greater<P> > que; 
    //pair第一个元素存的是dis[i]，第二个元素存的是i，也就是可达的节点; 
    //pair比较大小是先比较first，也就是比较dis，符合dij算法要求。 
	dis[start]=0;
    que.push(P(0,start));//很神奇的一种pair构造方法 
    while(!que.empty()){
    	//取出堆顶元素 
        P p = que.top();//拿出队首元素
        que.pop();
        int v=p.second;
        /*下面这句话是个优化，本来 dis[v]和p.first应该是相等的，
		如果不相等就代表着这个节点在放入队列之后又被更新了。举个例子，
		比如从点2到点3你第一次存的dis是3，如果dis=3存入之后，点2到点
		3的最短距离又被更新成2，就又会存一个dis=2进到队列里面，如果
		我们按照dis=3松弛一边，那么轮到dis=2的时候就又要松弛一边，这
		和直接按照dis=2松弛效果是一样的，所以我们不如直接去根据dis=2
		松弛好了。*/ 
        if(dis[v]<p.first)continue;
        //遍历v能到的所有点
        for(int i=head[v];i!=-1;i=edge[i].nex){
            node e=edge[i];
            
            //如果可以松弛，直接更新。 
            if(e.w+dis[v]<dis[e.to]){
                dis[e.to]=e.w+dis[v];
                que.push(P(dis[e.to],e.to));
            }
        }
    }
}

//主函数
signed main()
{
	int n,m;
	while(cin>>n>>m){
		if(n==0&&m==0)break;
		init();
		for(int i=0;i<m;++i){
			int u,v,w;
			cin>>u>>v>>w;
			//无向图正反存两次，有向图存一次 
			add(u,v,w);
			add(v,u,w);
		}
		dij(1);
		cout<<dis[n]<<endl;
	}
    return 0;
}

优缺点

优点 缺点
跑单源点可以高达 10000 多源点跑多次
复杂度比较适中 不能跑有负权的图

Bellman-Ford算法

类似于链式前向星表的发现，总可以换个角度去解决问题

问题引入：上面的两个算法一直着重于找中转点来进行松弛，我们能不能不管中转点呢？当然可以。我们之前的策略是找一个中转点，然后用它连的边实现松弛。我们现在不用中转点，我们可以找路径，比如dis[i]就是一个路径，它代表从出发点到i点的路径的距离

思路1：我们每次拿我们已知的可能的最短路径 dis[k] 来进行松弛：如果 dis[k]+w[k][j]<dis[j] ，则刷新 dis[j] 。这样一轮下来，我们可以得到一些新的最短路径，我们再利用这些最短路径来松弛，又可以得到新的最短路径，通过这样的方式一层一层建立起整个最短路的结构

还是松弛操作，但是不再是枚举点取松弛而是枚举边

每次松弛操作实际上是对相邻节点的访问，那么第 n 次松弛操作保证了所有深度为n的路径最短

思考2：这样的操作要进行多少轮呢？不难想到，n 个点的图，最短路径上最多有 n-1 条边(链),所以最多进行n-1轮。但是，我们可以在一轮结束以后判断：当前这一轮进行松弛，如果有，那才有继续下一轮的必要，如果没有，那就可以提前退出了，因为你已经没有任何一条路径可以再进行松弛了，你再下一轮只是再进行一轮完全相同的操作

这篇Bellman-ford解决最短路和负权环的博客有详细的思路讲解和图示

注意：因为以边为对象，所以该算法要通过链式前向星存边实现

寻找最短路径

1
2
3
4
5
6
7
/*简短重要，核心代码*/
for(int k=1;k<=n-1;k++){//n个顶点
    for(int i=1;i<m;i++){//m调边
        if(dis[v[i]]>dis[u[i]]+w[i])
        dis[v[i]]= dis[u[i]]+w[i];
    }
}

注意：这里是应用链式前向星表以边为主体进行的计算。整个算法用一句话概括就是：对所有的 m 个边进行 n-1 次松弛操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*样例代码*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;

signed main(){
    int u[100],v[100],w[100],dis[100],n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    dis[i]=inf;
    dis[1]=0;
    for(int k=1;k<=n-1;k++){
		for(int i=1;i<=m;i++)
            if(dis[v[i]]>dis[u[i]]+w[i])
            dis[v[i]]=dis[u[i]]+w[i];
	}

    for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";
    return 0 ;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

寻找负权环路

除此之外，bellman-ford算法还可以检测出一个图是否含有负权回路。如果进行 n-1 轮松弛操作之后仍然存在

1
2
if(dis[v[i]]>dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]] + w[i];

的情况，也就是说在进行n-1轮松弛后，仍可以继续成功松弛，那么此图必然存在负权回路。如果一个图没有负权回路，那么最短路径所包含的边最多为 n-1 条，即进行 n-1 轮松弛操作后最短路不会再发生变化。如果在 n-1 轮松弛后最短路仍然可以发生变化，则这个图一定有负权回路

模板

显然Bellman-Ford算法的时间复杂度是 O(nm) ，这个时间复杂度貌似比Dijkstra算法还要高，我们还可以对其进行优化。在实际操作中，Bellman-Ford算法经常会在未达到 n-1 轮松弛前就已经计算出最短路，之前我们已经说过，n-1 其实是最大值。因此可以添加一个一维数组用来备份数组 dis 。如果在新一轮的松弛中数组 dis 没有发生变化，则可以提前跳出循环，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//优化后的样例代码(附带检查负权回路)
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

signed main()
{
    int u[100],v[100],w[100],dis[100],n,m,ck,flag;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
	cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    dis[i]=INF;
    dis[1]=0;
    for(int k=1;k<=n-1;k++){
        ck=0 ;//用来标记本轮松弛操作中数组dis是否会发生更新
        for(int i=1;i<=m;i++){
            if(dis[v[i]]>dis[u[i]]+w[i]){
                dis[v[i]]=dis[u[i]]+w[i];
                ck=1;//数组dis发生更新，改变check的值
            }
        }
        if(ck==0)break;//如果dis数组没有更新，提前退出循环结束算法
    }
    flag=0;
	//判断负权环路
    for(int i=1;i<=m;i++)
    if(dis[v[i]]>dis[u[i]]+w[i])flag=1;
	if(flag==1)
	printf("此图包含有负权回路\n");
	else{
		for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	}
    return 0 ;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

Bellman-Ford算法堆优化（ SPFA ）

思路：很多时候我们并不需要那么多无用边去尝试进行松弛操作。这时候就不再看边了，而是改用看点，如果 dis[i] 刷新了，那么说明这个 i 点可以为我们接下来的松弛提供帮助，我们应该将它记录起来。那么我们用队列来维护“可能会引起松弛操作的点”，进而就可以只访问必要的边了，从而省去没必要的操作。

注意：这个队列里的元素是可能重复入队的，因为一个点的最短路径可以不断更新。另外当一个点已经在队列里的时候，我们是不用将它入队的，因为我们记录这个点的目的是等会要使用它去更新其他点，所以我们只用记录一次编号

这里一定要和 dijkstra 的堆优化分清楚， dijkstra 堆优化的队列里面存的是某一长度的边。而我们这里不需要，所以就算这个点的最短路径中间可能会变但是不影响我们的结果，我们只需要记住这个点可能可以作为松弛的中转点，也就是我们可以用它进行松弛就够了。具体实现操作看课件很详细

寻找最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*关键核心*/
void SPFA(ll s){
	//不同源点初始化
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	vis[s]=1;
	//起点入队
	queue<ll> q;
	q.push(s);
	while(!q.empty()){
		//取队首元素
		 ll now=q.front();
		 q.pop();
		 //顶点出队，标记为0，代表不在队里
		 vis[now]=0;
		 //链式前向星表遍历now点所能达到的所有点
		 for(int i=head[now];i!=-1;i=nex[i]){
		 	//判断是否可以松弛，可以就更新答案
			 if(dis[to[i]]>dis[now]+weight[i]){
			 	dis[to[i]]=dis[now]+weight[i];
			 	//判断这个点是否在队列里，不在就入队
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=1;
				} 
			} 
		} 
	} 
}

寻找负权环路

Bellman-Ford算法可以寻找负权回路，当然SPFA算法也可以了，而且思路都差不多

  • 思路一：判断如果一个点入队次数超过 n ，那么就存在负环（相当于松弛最多 n-1 一次）

  • 思路二：判断起点到 i 的最短路所包含的点的个数

对于思路一网上有人说他不好，因为如果出现输入自己到自己的边，或者出现重边的情况（可以自己思考一下为什么）就会误判，所以用思路二更加保险

思想：首先我们要知道，对于一个不存在负环的图，从起点到任意一个点最短距离经过的点最多只有 n 个。这样的话，我们用 tot[i]表示从起点（假设就是 1）到 i 的最短距离包含点的个数，初始化 tot[1]=1 ，那么当我们能够用点 u 松弛点 v 时，松弛时同时更新 tot[v]=cnt[u]+1 ，若发现此时 tot[v]>n ，那么就存在负环

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*附带寻找负权回路*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll V=1005;
const ll E=5005;

//链式前向星非结构体写法，weight,to,nex元素一一对应
ll weight[E],to[E],nex[E];
bool vis[E];//注意这个标记数组和dijkstra的不太一样，这个是用来标记不在队里的点
ll cnt=0;//寄存指针

ll n,m,dis[V];//dis数组存起来到i点的最短距离
ll head[V];
bool tot[V];

//加边
void add(ll u,ll v,ll w){
	cnt++;
	to[cnt]=v;
	weight[cnt]=w;
	nex[cnt]=head[u];
	head[u]=cnt;
} 

//存图初始化
void init(){
	cnt=0;
	memset(head,-1,sizeof(head)); 
} 

bool SPFA(ll s){//因为要判断所以改为bool型
	//不同源点初始化
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	vis[s]=1;
	tot[s]=1;
	queue<ll> q;
	q.push(s);//起点入队
	while(!q.empty()){
		 ll now=q.front();//取队首元素
		 q.pop();//顶点出队，标记为0，代表不在队里
		 vis[now]=0;
		 
		 for(int i=head[now];i!=-1;i=nex[i]){//链式前向星表遍历now点所能达到的所有点
		 	 //判断是否可以松弛，可以就更新答案
			 if(dis[to[i]]>dis[now]+weight[i]){
			 	dis[to[i]]=dis[now]+weight[i];
				tot[to[i]]=tot[now]+1;
				//判断是否找到负权回路
				if(tot[to[i]]>n)
				return 1;
			 	//判断这个点是否在队列里，不在就入队
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=1;
				} 
			} 
		} 
	} 
	return 0;
}

优缺点

优点 缺点
也可以跑顶点数较多的图 最坏复杂度太高跑稠密图可能被卡 TLE
可以跑带有负权的图

最短路算法注意问题

  • 注意初始化问题，到底哪些数组、变量需要初始化，什么时候初始化。包括 dijkstra 算法、SPFA 算法等。还有编号是从 1 开始还是 0 开始

  • 有的题会有重边，邻接矩阵需要将输入值和已经存在的边权取一下 min

  • 因为 SPFA 算法最坏情况下的时间复杂度是 O(NM) ，所以有时会被恶意数据卡掉（网格图），如果没有负边权的话还是建议优先使用Dijkstra

  • 在有负边权的图上跑单源最短路一般使用 SPFA

  • 判断负权环路用 SPFA

  • 超级源点使用以及最短路回溯路程

比较总结

  • 顶点数少多源点的题就用 Floyd
  • 顶点数多且没有负权的正常题 dijkstra 足矣（不容易被卡掉）
  • 带负权的图或者找负权回路就 SPFA

常见拓展

超级源点

  • 有一些题可能会出现多个起点出发的情况，那就和网络流一样建立一个超级源点，然后让这个超级源点到这几个起点的权值为 0 ，然后拿超级源点跑最短路

  • 那要是多个终点可以用同样的方法从终点建立一个超级汇点，或者是把超级汇点当做超级源点，把图翻过来倒着跑一边

  • 更变态的超级源点和超级汇点一起

最短路回溯路程

就是想办法把找到的最短路的走法记下来

  • Floyd 回溯用一个二维数组记录走过的中途节点

模板题：给出 n 个点 m 条边找出最短路径和走过的路程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*floyd记录路径：https://blog.csdn.net/faithdmc/article/details/22991605/
和迪杰斯特拉记录前面节点不一样，这个可以用二维数组记录，好理解也好用
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3,inf=0x3f3f3f3f;

int n;
int a[N][N],b[N];
int way[N][N];//记录从当前点到下一个点需要经过的点
int graph[N][N],dp[N][N];

void Floyd(){
	//初始化dp数组
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		dp[i][j]=graph[i][j];//没有中转点,最短距离就是两点的边权 
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dp[i][k]+dp[k][j]+b[k]<dp[i][j])
                dp[i][j]=dp[i][k]+dp[k][j]+b[k],way[i][j]=way[i][k];//注意不是k因为当前的缩进道路可能已经被更新过了
                else if(dp[i][k]+dp[k][j]+b[k]==dp[i][j]&&way[i][k]<way[i][j])
                way[i][j]=way[i][k];
            }
		}
	} 
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n&&n){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int x;cin>>x;
                if(x==-1)graph[i][j]=inf;
                else graph[i][j]=x;

                way[i][j]=j;
            }
        }
        for(int i=1;i<=n;i++)
        cin>>b[i];
        Floyd();
        int x,y;
        while(cin>>x>>y){
            if(x==y&&y==-1)break;
            printf("From %d to %d :\nPath: ",x,y);
            int ans=x;
            while(ans!=y){
                printf("%d-->",ans);
                ans=way[ans][y];
            }
            printf("%d\nTotal cost : %d\n\n",y,dp[x][y]);
        }
    }
    //system("pause");
    return 0;
}
  • 其他的算法用一个一维数组记录每个点的前继节点

记录前继节点后，从终点向起点遍历并通过 stack 颠倒一下顺序输出就好了

注意：一维数组记录后继节点直接从起点遍历输出想法很好但是大错特错

模板题：给出 n 个点 m 条边找出最短路径和走过的路程，没有输出 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll inf = 0x3f3f3f3f3f3f;
typedef pair<ll,ll> P;//用 P代替 pair<ll,ll>
//pair可以理解成一个讲两个变量捆绑起来的东西 
const ll V = 2e5+5;//最大顶点数
const ll E = 2e5+5;//最大边数 
ll dis[V],head[V],pre[V];
bool vis[V];
struct node{
    ll nex,to,w;
}edge[E];
ll cnt;

void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
    memset(pre,0,sizeof pre);
}

inline void add(ll u,ll v,ll w){//内联函数加快速度 
    cnt++;
    edge[cnt].nex=head[u];
    head[u]=cnt;
	edge[cnt].to=v;
    edge[cnt].w=w;
}

void dij(ll start){
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));//初始化放在init()里也可以
	//定义优先队列存 pair，小顶堆，注意最后两个尖括号间必须有空格。 
    priority_queue<P,vector<P>,greater<P> > que; 
    //pair第一个元素存的是dis[i]，第二个元素存的是i，也就是可达的节点; 
    //pair比较大小是先比较first，也就是比较dis，符合dij算法要求。 
	dis[start]=0;
    que.push(P(0,start));//很神奇的一种pair构造方法 
    while(!que.empty()){
    	//取出堆顶元素 
        P p = que.top();//拿出队首元素
        que.pop();
        ll v=p.second;
        
        /*下面这句话是个优化，本来 dis[v]和p.first应该是相等的，
		如果不相等就代表着这个节点在放入队列之后又被更新了。举个例子，
		比如从点2到点3你第一次存的dis是3，如果dis=3存入之后，点2到点
		3的最短距离又被更新成2，就又会存一个dis=2进到队列里面，如果
		我们按照dis=3松弛一边，那么轮到dis=2的时候就又要松弛一边，这
		和直接按照dis=2松弛效果是一样的，所以我们不如直接去根据dis=2
		松弛好了。*/ 
        if(dis[v]<p.first) continue;
        
        //遍历v能到的所有点。 
        for(ll i=head[v];i!=-1;i=edge[i].nex){
            node e=edge[i];
            //如果可以松弛，直接更新。 
            if(e.w+dis[v]<dis[e.to]){
                dis[e.to]=e.w+dis[v];
                pre[e.to]=v;
                que.push(P(dis[e.to],e.to));
            }
        }
    }
}
//主函数
signed main()
{
	ll n,m;
	while(cin>>n>>m){
		init();
		for(ll i=0;i<m;++i){
			ll u,v,w;
			cin>>u>>v>>w;
			//无向图正反存两次，有向图存一次 
			add(u,v,w);
			add(v,u,w);
		}
		dij(1);
		if(dis[n]>=inf)cout<<-1<<endl;
        else{
            ll ans=n;
            stack<ll> sta;
            while(pre[ans]){
                sta.push(pre[ans]);
                ans=pre[ans];
            }
            while(!sta.empty()){
                cout<<sta.top()<<" ";
                sta.pop();
            }
            cout<<n<<endl;
        }
	}
    return 0;
}