最短路径问题

在图论中的一个经典问题，求从图中一个点出发到另一个点所经过的所有边的总花费(边权)的最小。

图的存储

给定若干点和每两点之间的权值，需要用适当的方式把图中数据转化成特定的数据结果进行存储。常见的方式有邻接矩阵和邻接表，可根据具体的顶点和边数的大小进行灵活选择。也可借助向量容器进行存储，还有一种经典的高效存储方式，链式前向星。

邻接矩阵

邻接矩阵就是用一个二维数组G[ i ] [ j ]表示顶点i和j之间的边权，考虑重边问题时较为简单，只需加个判断语句。

  • 对已确定的边进行操作，效率高 数组的随机访问。

  • 易处理重边

    你可以随时覆盖掉重边，可以自己实现存储最最大（小）权的重边的边，只需加个判断语句

  • 过高的空间复杂度

    对于顶点数V，邻接矩阵存图的空间复杂度高达O(V2)**，顶点数上了一万可以不用考虑这种存图方式了。
    **对于稀疏图来说，邻接矩阵存图内存浪费太严重，这也是邻接矩阵存图在ACM题目中十分罕见的根本原因。

  • 对于不确定边的查询效率一般

    比如，我找个编号为1出发的第一条边我还要一条条边判断是否存在（权值是否为0）。

邻接表

邻接表就是位每个顶点建立一条单链表，链表上的存放与该顶点相连的点和边权，用得相对少。

一般邻接表会借助向量容器Vector实现

1
2
3
4
5
6
const int N=1e5+5;
vector<int> G[N];
void addedge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=1e5+5;
struct Edge{
	int v,w;
    Edge(){/*也可写构造函数创建Edge*/}
};
Edge make_Edge(int v,int w){
	Edge cur;cur.v=v;cur.w=w;return cur;
}
vector<Edge> G[N];
void addedge(int u,int v,int w){
	G[u].push_back(make_Edge(v,w));
	G[v].push_back(make_Edge(u,w));
}

//利用pair：
vector<pair<int,int> >G[N];
void addedge(int u,int v,int w){
	G[u].push_back(make_pair(v,w));
	G[v].push_back(make_pair(u,w));
}

  • 容器存储方便，可直接调用STL中的一些函数，例如排序
  • 缺点是速度可能会慢一些，并且vector会比数组的方式更费空间。
  • 内存利用率较高,对于顶点数V与边数E，**空间复杂度为O(V+E)**。能较好处理稀疏图的存储。
  • 对不确定边的操作方便效率也不错, 比如，要遍历从某点出发的所有边，不会像邻接矩阵一样可能会遍历到不存在的边。

链式前向星

这篇博客讲的挺好的

最终构建的链表结构：

此处缺一张图

其实就是邻居表的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N=1e5+5;
struct Node {
	int v;
	int w;
	int next;
}edge[M];
int head[N];
int cnt=0;
void add(int u,int v,int w)
{
    edge[cnt].w = w;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

优点

  • 内存利用率高

  • 对不确定边的操作方便效率也不错

    这点和邻接表一样，不会遍历到不存在的边。

缺点

  • 重边不好处理

    这点与邻接表一样，只有通过遍历判重。

  • 对确定边的操作效率不高

    也与邻接表一样，不能通过两点马上确定边，只能遍历查找。

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
31
32
33
34
const int N = 105;
const int INF = 1e9;
int maps[N][N];
int d[N];
int visit[N];
int n;

void init()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			maps[i][j] = INF;
	for (int i = 1; i <= n; i++)
		visit[i] = 0;
}
void dijkstra()
{
	for (int i = 1; i <= n; i++)
		d[i] = maps[1][i];
	d[1] = 0;
	visit[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		int t = -1;
		for (int j = 2; j <= n; j++)//这个循环是找到距离起点(集)最近的点
			if (!visit[j] && (t == -1 || d[t] > d[j]))
				t = j;
		if (t == -1)return;
		visit[t] = 1;
		for (int j = 2; j <= n; j++)//用找到的点去更新到其它顶点的最短路径
			if (!visit[j] && d[j] > d[t] + maps[t][j])
				d[j] = d[t] + maps[t][j];
	}
}

时间复杂度为O(n^2)，适合稠密图，用邻接矩阵

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
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
int const N = 2e5+10, M = 8e5+10;
int const INF = 0x3f3f3f3f;
int h[N],d[N],visit[N];
int cnt = 0;	//用于前向星建图
struct Node {
	int v;	//u->v中的v当前顶点
	int w;	//u->v的权值
	int next;//下一个u->next
}e[M];
inline void add(int u, int v, int w)	//前向星建图
{
    //尽管有重边的时候，会保存所有重边
    //入队列后，当最小的边重边出队列后会在vis中标记，因此后续的边出队列后将不会被处理
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = h[u];
	h[u] = cnt++;
}
//定义一个结构体用于优先队列中比较，也可在此重载()运算符
struct Cmp {	
	int  w, v;
	Cmp(int ww, int vv):w(ww),v(vv) {}
	bool operator < (const Cmp  a) const{
		return w > a.w;
	}
};
//也可通过pair<int,int>，需要注意的是要把权值w放于第一个Int中，并且在新建队列时第三个参数指定升序greater<pair<int,int> >
/*
	typedef pair<int,int> PII;
	priority_queue<PII, vector<PII>, greater<PII>> heap;
*/

void dijkstra()
{
	memset(visit, 0, sizeof(visit));
	memset(d, 0x3f, sizeof(d));
	priority_queue<Cmp> q;	
	q.push(Cmp(0,1));
	d[1] = 0;
	while (q.size())
	{
		int t = q.top().v;
		q.pop();
		if (visit[t])continue;
		visit[t] = 1;
		if (t == n)break;
		for (int i = h[t]; ~i; i = e[i].next)
		{
			int v = e[i].v;
			int w = d[t] + e[i].w;
			if (d[v] > w ) {
				d[v] = w;
				q.push(Cmp(d[v],v));
			}
		}
	}
}

时间复杂度 O(mlogn) 适合稀疏图

Bellman-ford算法

BF算法，动态规划的思想，首先将每个起始点和各个点之间的距离记录下来，并且枚举各个边不断对原记录优化（如果一个点的起点加上某一条边的费用小于前面用无论什么方法得到的费用，那么这点就是局部最优的），反复把每个点的情况进行枚举，每个点最多枚举m次，时间复杂度就是O( mn )，枚举完后，可以再遍历一遍，若出现有一点，走他，比不走他话费的钱要多，就说明这个图里存在负权环

和dijkstra很像 但是这里是沿着边进行松弛操作，用每条边来松驰源点到其它点的路径值，算法的正确性证明待理解。

1
2
3
for(int i = 0;i < n;++i)//枚举顶点
      for each(i,j)//对于每一条边
            deal(i,j)//松弛操作
1
2
3
4
5
6
7
8
9
10
11
12
13
//核心代码实现
void BF(int u)
{
	memset(d,0x3f,sizeof(d));
	d[u] = 0;
	for(int i = 1;i < n;++i){//枚举顶点
        //cnt存的是边的条数
		for(int j = 1;j <= cnt;++j){//对于每个i，看能否通过其它边来松驰源点到它的距离
			int x = a[j].from,y = a[j].to,z = a[j].dis;
			d[y] = min(d[y],d[x] + z);//松弛操作
		}
	}
}

判断负环：因为每个顶点最多松驰n-1次，若进行了n-1次松驰后，仍然可以松驰说明存在负环

1
2
3
4
5
6
7
bool check(){
	for(int i = 1;i <= cnt;++i){
		int x = a[i].from,y = a[i].to,z = a[i].dis;
		if(d[y] < d[x] + z)return 1;
	}
	return 0;
}

一般不会使用BF算法，时间复杂度过高，一般会用spfa算法，可以理解为BF算法的优化

Spfa算法

在bellman_ford当中会将所有的边进行松弛操作，但其实没有必要，只有那些已经松弛过的点才可能去松弛别的点，所以我们可以用一个队列来记录松弛成功了的点，以此用这些点来松弛邻接点

关于spfa的详细解释可见：https://blog.csdn.net/sxy201658506207/article/details/78779045

此处附上一道模板题的题解

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int const N = 110, M = 1e4+5;
int const INF = 0x3f3f3f3f;
int h[N],d[N],visit[N];
int cnt = 0;	//用于前向星建图
int n,start,des;
struct Node {
	int v;
	int w;
	int next;
}e[M];

void add(int u, int v, int w)
{
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = h[u];
	h[u] = cnt++;
}

int spfa()
{
	memset(visit, 0, sizeof(visit));
	memset(d, 0x3f, sizeof(d));
	queue<int> q;
	q.push(start);
	d[start] = 0;
	while (q.size())
	{
		int t = q.front();
		q.pop();
		visit[t] = 0;
		for (int i = h[t]; ~i; i = e[i].next)
		{
			int v = e[i].v;
			int w = d[t] + e[i].w;
			if (d[v] > w ) {
				d[v] = w;
				if (!visit[v]) {
					q.push(v);
					visit[v] = 1;
				}
			}
		}
	}
	return d[des];
}

int main()
{
	memset(h, -1, sizeof(h));
	scanf("%d%d%d", &n, &start, &des);
	for (int i = 1; i <= n; i++)
	{
		int num;
		scanf("%d", &num);
		int cnt = 1;
		while (num--)
		{
			int v;
			scanf("%d", &v);
			if (cnt == 1)
				add(i, v, 0);
			else add(i, v, 1);
			cnt++;
		}
	}
	int ans = spfa();
	if (ans != INF)printf("%d\n",ans );
	else printf("-1\n");
	return 0;
}

判断负环(正环)

每个点最多更新n次，若发现有若发现有某个点入队次数超过n，则说明有负环，因此只需要加一个数组记录每个点的入队次数即可

SPFA算法有两个优化算法 SLF 和 LLL：SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。

LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。

引用网上资料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。（此处文字来源，侵删）

Floyd算法

求多源最短路径

核心代码实现：

1
2
3
4
5
for(int k=1;k<=n;++k)//枚举中转点
    for(int i=1;i<=n;++i)//枚举边的起点
        for(int j=1;j<=n;++j)//枚举边的终点
            if(a[i][j]>a[i][k]+a[k][j])//松弛操作（即利用第三个点来判断是否可以更新目标两个点的最短距离）
                a[i][j]=a[i][k]+a[k][j];//a[i][j]是从i到j的最小值

关于k为什么要枚举在第一层循环:
刚才已经说过floyd类似于dp，而k就是dp的阶段（dp的阶段显然要枚举在第一层的），其实a本来是三维a[k][i][j]表示只经过前k个点从i到j的最短路，而可以将第一维的k舍去（like背包） 所以就成了现在的样子啦

求闭包

1
2
3
4
5
6
for(int k=1;k<=n;k++)	//floyd算法
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (maps[i][k] == 1 && maps[k][j] == 1)
					maps[i][j] = 1;

判负环（正环）

1
2
3
4
5
6
7
8
9
10
11
12
bool floyd()
{
	for(int k=1;k<=n;k++)
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				if (maps[i][j] > maps[i][k] + maps[k][j])
					maps[i][j] = maps[i][k] + maps[k][j];
			if (maps[i][i] < 0)return true;
		}
	return false;
}

例题 例题2

最短路算法对比

适用情况：是否适用有向图，待了解！！！

最短路算对比

（图片来源，侵删）

参考：https://my.oschina.net/u/4353003/blog/4335488

https://optimjie.github.io/2019/11/24/%E6%9C%80%E7%9F%AD%E8%B7%AF%E6%A8%A1%E6%9D%BF/

http://jzqt.github.io/2015/07/21/ACM%E5%9B%BE%E8%AE%BA%E4%B9%8B%E5%AD%98%E5%9B%BE%E6%96%B9%E5%BC%8F/