单/多源最短路

发表于 | 阅读数

单/多源最短路的三种算法 — dijkstra & spfa & floyd

什么是最短路

单源最短路：计算图中一个点到其他各点的最短距离
多源最短路：计算图中多个点到其他各点的最短距离

单源最短路 — dijkstra 算法

算法描述

main 函数：用vector数组存边，初始化一维数组 dist 来表示起点到其他各点的距离（到自己为 0，其他点为 INF），将初始边（目标点为起点，权值为 0）加入到优先队列 queue 中
dijkstra 函数：抛出优先队列的 top 边，若这个边的权值比现在到这个目标点的权值大（说明起点到该点的长度又更新了，而且那个边肯定在这个边前面），就跳过，否则就疏松以这个点为起点的所有边，若通过这个点，起始点到其他的点的距离有减小的，则把路径减小的目标点和减小后的距离加入到优先队列中，重复操作

算法应用

说明：这个题有点意思（

题目描述

知识点：最短路，最短路的优化

贝克兰德有n个城镇，这些城镇之间有m条道路连接，每条道路有一个长度l。

zf在其中k个城镇设置了治安点。当一个城镇发生事件时，任意一个治安点都可以派人前往。但是为了节省资源，往往会选择距离最近的治安点。

那么请问，对于每一个城镇，最近的治安点距离为多少。

思路

这个题要求算部分点到其他点的最短距离，因此看起来是一个多源最短路，但是你如果执行多次 dijkstra 你就超时了，所以我们要多设立一个虚拟点 s，把所有的治安点往这个虚拟点上拉一条距离为 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
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
98
99
100
101
102
/* 
 Author: 王振
 Result: AC	Submission_id: 1833390
 Created at: Fri Sep 13 2019 21:01:55 GMT+0800 (CST)
 Problem_id: 2378	Time: 540	Memory: 5508
*/

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,s;
int dist[1005];
struct line{
    int w;
    int v;
    bool operator <(const line&b) const
    {
    	return w>b.w;
	}
}list;

vector <line> vec[1005];
priority_queue <line> q;

void dijkstra(int p)
{
	list.v=p;
	list.w=0;
	q.push(list);
	while(!q.empty())
	{
		struct line k=q.top();
		q.pop();
		if(k.w>dist[k.v])
		{
			continue;
		}else
		{
			for(int i=0;i<vec[k.v].size();i++)
			{
				struct line j=vec[k.v][i];
				if(dist[j.v]>dist[k.v]+j.w)
				{
					dist[j.v]=dist[k.v]+j.w;
					list.v=j.v;
					list.w=dist[j.v];
					q.push(list);
				}
			}
		}
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int u,v,w;
		scanf("%d%d%d",&n,&m,&s);
		for(int i=1;i<=n+1;i++)
		{
			while(!vec[i].empty())
			{
				vec[i].pop_back();
			}
		}
		for(int i=1;i<=n+1;i++)
		{
			dist[i]=10000000;
		}
		for(int i=1;i<=s;i++)
		{
			scanf("%d",&u);
			list.w=0;
			list.v=u;
			vec[n+1].push_back(list);
			list.v=n+1;
			vec[u].push_back(list);
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			list.v=v;
			list.w=w;
			vec[u].push_back(list);
			list.v=u;
			vec[v].push_back(list);
		}
		dist[n+1]=0;
		dijkstra(n+1);
		for(int i=1;i<=n;i++)
		{
			printf("%d ",dist[i]);
		}
		printf("\n");
	}
	return 0;
}

单源最短路 — spfa 算法 可以判断负环！

算法描述

将某个点的序号 x 作为 spfa 函数的输入，则从这个点开始进行单源最短路，如果点 v 通过当前点 u 到输入点 x 的距离变小，那么更新距离值，并且如果 v 不在队列中，就将 v 加入到队列里，对于每个点记录它们加入队列的次数，如果大于总点数 n ,就判定为当前图中存在负环。

题目描述

知识点：最短路

克莱恩在一场冒险中得到了得到了一个破损的魔法阵，这个魔法阵是一个有n个点m条边的有向有环图，任意两点之间最多只有一条边，每条边有一个能量值a（可能是负数，别问问就是magical），不存在负环。

克莱恩试图去修补这个魔法阵。已知，这个魔法阵缺少了3条边，且已经知道这3条边的起点和终点（有向）。对于每条边，克莱恩要赋予其一个能量值c，为了避免邪神出现，修补过程以及结束后也不能出现负环。

请问每次的最小花费是多少(保证有解，可以是负数)。

题目思路

修补过程及结束后不能出现负环，则枚举边权来找到最大的可以使图中出现负环的权值，那么给这个权值加一图中就没有负环（其实可以二分权值直接找到答案）

代码示例

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
/* 
 Author: 王振
 Result: AC	Submission_id: 1833275
 Created at: Fri Sep 13 2019 16:22:27 GMT+0800 (CST)
 Problem_id: 2376	Time: 790	Memory: 3228
*/

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct edge{
	int v,w;
}e;

vector <edge> v[305];
queue <int> q;
int n,m;
int flag=0;                // 有无负环的标志，有负环 flag=1 
int num[305];              // 存储每个点加入队列的次数 
int visit[305];			   // 如果某个点在队列中，那么visit[i]=1，反之为0 
int dist[305];			   // 存储距离 

void spfa(int x)
{
	for(int i=0;i<n;i++)          // 初始化 
	{
		num[i]=0;
		visit[i]=0;
		if(i!=x) dist[i]=10000000;
	}
	while(!q.empty())
	{
		int a=q.front();
		visit[a]=0;
		q.pop();
		for(int i=0;i<v[a].size();i++)
		{
			int c=v[a][i].v;
			if(dist[c]>dist[a]+v[a][i].w)    // 距离小于当前距离，更新，如果这个点不在队列中则加入队列，且这个点的访问次数+1 
			{
				dist[c]=dist[a]+v[a][i].w;
				if(visit[c]==0)
				{
					num[c]++; 
					q.push(c);
					visit[c]=1;
				}
			}
		}
		for(int i=0;i<n;i++)
		{
			if(num[i]>n)            // 如果对一个点访问次数 >n 则判定为存在负环 
			{
				flag=1;
				return;
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	int x,y,z;
	for(int i=0;i<m;i++)         // 输入边 
	{
		cin>>x>>y>>z;
		e.v=y;
		e.w=z;
		v[x].push_back(e);
	}
	for(int i=0;i<3;i++)
	{
		flag=0;
		cin>>x>>y;
		e.v=y;
		e.w=1000;
		v[x].push_back(e);
		while(flag==0)        // 若没有负环则边权减小直到有负环为止
		{
			q.push(x);
			e.w--;
			v[x].pop_back();
			v[x].push_back(e);
			spfa(x);
		}
		v[x].pop_back();      //此时的边权为最大的有负环的权值，加一则没有负环
		e.w++;
		v[x].push_back(e);
		cout<<e.w<<endl;
	}
	return 0;
}

多源最短路 — floyd 算法

算法描述

floyd 算法很简单，先在邻接矩阵中将直接相连的边的权值更新，然后对于任意两个点，以任意一个点为中介，更新两个点之间的权值，注意将当成中介的点放在最外面的循环，如若不然，可以将这三个循环执行三遍，则不用管i,j,k的顺序

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for(int k=1;k<=n;k++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(dist[i][j]>dist[i][k]+dist[k][j])
			{
				dist[i][j]=dist[i][k]+dist[k][j];
			}
		}
	}
}