CoderZQYのBlog

个人不定期更新的学习周报

0%

链式前向星+SPFA

发表于 分类于

算法笔记1——链式前向星+SPFA+Dijkstra

题目链接：[P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]

1、题目描述（入门）

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n, m, s分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u, v, w表示一条 u→v 的，长度为 w 的边。

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。

输入输出样例

输入

1
2
3
4
5
6
7
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出

1
0 2 4 3

数据范围：对于 100% 的数据：1 ≤ n ≤104，1 ≤ m ≤ 5×105，保证数据随机。

2、链式前向星

本题根据数据边数m<=500000，邻接矩阵存不下，只能使用静态邻接表存储。

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》

链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。

对于下面的数据，第一行5个顶点，7条边。接下来是边的起点，终点和权值。也就是边1 -> 2 权值为1。

1
2
3
4
5
6
7
8
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7

链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 //以1为起点的边的集合
1 5 6
1 3 4
1 2 1
 
2 //以2为起点的边的集合
2 3 2
 
3 //以3为起点的边的集合
3 4 3
 
4  //以4为起点的边的集合
4 5 7
4 1 5
 
5 //以5为起点的边不存在

我们先对上面的7条边进行编号第一条边是0以此类推编号【0~6】，然后我们要知道两个变量的含义：

  • Next，表示与这个边起点相同的上一条边的编号。
  • head[ i ]数组，表示以 i 为起点的最后一条边的编号。

head数组一般初始化为-1，为什么是 -1后面会讲到。加边函数是这样的：

1
2
3
4
5
6
7
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}

我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：

  • 对于1 2 1这条边：edge[0].to = 2; edge[0].next = -1; head[1] = 0;
  • 对于2 3 2这条边：edge[1].to = 3; edge[1].next = -1; head[2] = 1;
  • 对于3 4 3这条边：edge[2].to = 4; edge[2],next = -1; head[3] = 2;
  • 对于1 3 4这条边：edge[3].to = 3; edge[3].next = 0; head[1] = 3;
  • 对于4 1 5这条边：edge[4].to = 1; edge[4].next = -1; head[4] = 4;
  • 对于1 5 6这条边：edge[5].to = 5; edge[5].next = 3; head[1] = 5;
  • 对于4 5 7这条边：edge[6].to = 5; edge[6].next = 4; head[4] = 6;

遍历函数是这样的：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++)//n个起点
{
    cout << i << endl;
    for(int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
    {
        cout << i << " " << edge[j].to << " " << edge[j].w << endl;
    }
    cout << endl;
}

第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过edge[ j ].next来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的edge[ j ].next为 -1做为终止条件。

3、SPFA（Shortest Path Faster Algorithm）

1. spfa的算法思想（动态逼近法）：

  • 设立一个先进先出的队列q用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
  • 松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对结点i,j进行松弛，就是判定是否dis[j]>dis[i]+w[i,j]，如果该式成立则将dis[j]减小到dis[i]+w[i,j]，否则不动。

和广搜bfs的区别：

SPFA 在形式上和广度(宽度)优先搜索非常类似，不同的是bfs中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进(重新入队)，于是再次用来改进其它的点，这样反复迭代下去。

2. 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void  spfa(s);  //求单源点s到其它各顶点的最短距离
    for i=1 to n do { dis[i]=∞; vis[i]=false; }   //初始化每点到s的距离，不在队列
    dis[s]=0;  //将dis[源点]设为0
    vis[s]=true; //源点s入队列
    head=0; tail=1; q[tail]=s; //源点s入队, 头尾指针赋初值
    while head<tail do {
       head+1;  //队首出队
       v=q[head];  //队首结点v
       vis[v]=false;  //释放对v的标记，可以重新入队
       for 每条边(v,i)  //对于与队首v相连的每一条边
  	  if (dis[i]>dis[v]+a[v][i])  //如果不满足三角形性质
	 	dis[i] = dis[v] + a[v][i]   //松弛dis[i]
		if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //不在队列，则加入队列
    }

3. 最短路径的输出？

  • 在一个图中，我们仅仅知道结点A到结点E的最短路径长度，有时候意义不大。这个图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？
  • 我们定义一个path[]数组，path[i]表示源点s到i的最短路程中，结点i之前的结点的编号(父结点)，我们在借助结点u对结点v松弛的同时，标记下path[v]=u，记录的工作就完成了。
  • 如何输出呢？我们记录的是每个点前面的点是什么，输出却要从最前面到后面输出，这很好办，递归就可以了：
1
2
3
4
void printpath(int k){
	if (path[k]!=0) printpath(path[k]);
	cout << k << ' ';
}

4. 完整题解代码

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
#include<bits/stdc++.h>
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
  int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码，不懂翻书看解释
  edge[++num_edge].next=head[from]; //链式存储下一条出边
  edge[num_edge].to=to; //当前节点编号
  edge[num_edge].dis=dis; //本条边的距离
  head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{
  queue<int> q; //spfa用队列，这里用了STL的标准队列
  for(int i=1; i<=n; i++) 
  {
    dis[i]=inf; //带权图初始化
    vis[i]=0; //记录点i是否在队列中，同dijkstra算法中的visited数组
  }
  q.push(s); dis[s]=0; vis[s]=1; //第一个顶点入队，进行标记
  while(!q.empty())
  {
    int u=q.front(); //取出队首
    q.pop(); vis[u]=0; //出队标记
    for(int i=head[u]; i; i=edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
    {
      int v=edge[i].to; 
      if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
      {
        dis[v]=dis[u]+edge[i].dis;
        if(vis[v]==0) //未入队则入队
        {
          vis[v]=1; //标记入队
          q.push(v);
        }
      }
    }
  }
}
int main()
{
  cin>>n>>m>>s;
  for(int i=1; i<=m; i++)
  {
    int f,g,w;
    cin>>f>>g>>w; 
    addedge(f,g,w); //建图，有向图连一次边就可以了
  }
  spfa(); //开始跑spfa
  for(int i=1; i<=n; i++)
    if(s==i) cout<<0<<" "; //如果是回到自己，直接输出0
      else cout<<dis[i]<<" "; //否则打印最短距离
  return 0;
} //结束

5、题目描述（进阶）

题目链接：P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。数据保证你能从 s 出发到任意点。

输入格式

第一行为三个正整数 n, m, s。 第二行起 m 行，每行三个非负整数 ui, vi, wi , 表示从 ui->vi 有一条权值为 wi 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

输入 #1

1
2
3
4
5
6
7
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

1
0 2 4 3

SPFA算法由于它上限 O(NM) = O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra.

6、dijkstra算法

  • dijkstra是一种单源最短路径算法, 时间复杂度上限为O(n2)(朴素), 在实际应用中较为稳定; 加上堆优化之后更是具有**O((n+m)log2n)**的时间复杂度, 在稠密图中有不俗的表现.

dijkstra的原理/流程?

  • dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
  • 我们把点分成两类,一类是已经确定最短路径的点,称为”白点”,另一类是未确定最短路径的点,称为”蓝点”
  • dijkstra的流程如下:
    1. 初始化dis[start] = 0, 其余节点的disdis值为无穷大.
    2. 找一个dis值最小的蓝点 x , 把节点 x 变成白点.
    3. 遍历 x 的所有出边(x,y,z), 若dis[y] > dis[x] + z, 则令dis[y] = dis[x] + z
    4. 重复2,3两步,直到所有点都成为白点..
  • 时间复杂度为O(n2)

dijkstra的正确性

  • 当所有边长都是非负数的时候,全局最小值不可能再被其他节点更新.所以在第2步中找出的蓝点 x 必然满足:dis[x]:已经是起点到 x 的最短路径.我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度
  • 缺点：不能处理有负权边的情况！

dijkstra的堆优化?

  • 观察dijkstra的流程,发现步骤2可以优化：

    我们可以用堆对dis数组进行维护, 用O(log2n)的时间取出堆顶元素并删除, 用O(log2n)遍历每条边, 总复杂度O((n+m)log2n)

7、完整代码

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

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
#include<iostream>
#include<queue>
using namespace std;
#define maxn 100005
#define maxm 500005
#define inf 2147483647
int n, m, s;
int dis[maxn], head[maxn], vis[maxn];
struct Edge {
	int next;
	int to;
	int weight;
}edge[maxm];
int edge_num = 0;
void addEdge(int f, int t, int w) {
	edge[++edge_num].next = head[f];
	edge[edge_num].to = t;
	edge[edge_num].weight = w;
	head[f] = edge_num;
}
struct node {
	int dis;
	int pos;
	bool operator <(const node& x) const{
		return dis > x.dis;
	}
}tmp;
void dijkstra() {
	priority_queue<node> q;
	tmp.dis = 0;
	tmp.pos = s;
	q.push(tmp);
	dis[s] = 0;
	while (!q.empty()) {
		tmp = q.top();
		q.pop();
		if (vis[tmp.pos]) {
			continue;
		}
		vis[tmp.pos] = 1;
		int u = tmp.pos;
		for (int i = head[u]; i; i = edge[i].next)
		{
			int v = edge[i].to;
			if (dis[v] > dis[u] + edge[i].weight) {
				dis[v] = dis[u] + edge[i].weight;
				if (!vis[v]) {
					tmp.dis = dis[v];
					tmp.pos = v;
					q.push(tmp);
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++)
	{
		int f, t, w;
		cin >> f >> t >> w;
		addEdge(f, t, w);
	}
	for (int i = 1; i <= n; i++)
	{
		dis[i] = inf;
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	return 0;
}
-------------本文结束感谢您的阅读-------------