最短路模板

发表于 | 更新于 | 分类于

dijkstra算法

dijstra邻接矩阵

时间复杂度: $O(n^2)$

与最小生成树prim算法的联系: d[1] = 0
最小生成树T、S集合每次从S中取出一个d[x]最小的来更新S中的所有点，
由于T中点在加入前与其他所有点已完成更新，所以不用更新T中的点。

dijkstra: 每次取出一个全局最小的d[x] (未访问过的点)，更新其他所有点

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 3010;
int a[N][N], d[N], n, m;		//邻接矩阵a，距离，n个点，m条边

bool v[N]; 				//标记数组 
void dijkstra()
{
	memset(d, 0x3f, sizeof(d));				//dist初始化为 -inf
	for(int i = 1; i < n; i ++ )	
			//顺序枚举每个点，最后一个点时d[n]已被其它所有点所更新，由于是无向图相当于这个点也更新了其它所有点，所以不用要n节点 
	{
		int x = 0;		//找到未标记dist节点中最小的
		for(int j = 1; j <= n; j ++ )	 
			if(!v[j] && (x == 0 || d[j] < d[x]))	x = j;
		v[x] = 1;
		for(int y = 1; y <= n; y ++ )		//用全局最小值更新其他节点	
			d[y] = min(d[y], d[x] + a[x][y]);
	}
}

int main()
{
	cin >> n >> m;			//n个节点，m条边  
	memset(a, 0x3f, sizeof(a));				//所有点距初始化为inf,即没有边相连 
	for(int i = 1; i <= n; i ++ )	a[i][i] = 0;	 //自己与自己没有边，距离为0; 
	for(int i = 1; i <= m; i ++ )	
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z); 		//起点 终点 权值 
		a[x][y] = a[y][x] = min(z, a[x][y]);	//由于可能两点之间多边，又是无向图，连两条边，更新两点之间的最短距离 
	}	
	prim();
	for(int i = 1; i <= n; i ++ )		//每个点的最短距离
		printf("%d\n", d[i]);
	return 0; 
}

dijkstra堆优化

时间复杂度: $(m + n)logn -> mlogn$

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
#include <iostream>
#include <algorithm>
#include <queue> 
#include <cstring>
using namespace std;
const int N = 5e2;			//顶点数 
const int M = 5e3;			//边数 
typedef pair<int, int> PII;
int n, m, tot;
int edge[M], ver[M], Next[M];
int d[N], head[N];
bool v[N];
void add(int x, int y, int z)	//见邻接表存图
{	
	ver[++ tot] = y;
	edge[tot] = z;
	Next[tot] = head[x];
	head[x] = tot;
}

void dijkstra()
{
	memset(d, 0x3f, sizeof(d));			//初始距离为inf 
	memset(v, 0 , sizeof(v));		//每个点没有被标记 
	priority_queue<PII> q;		//添-号变成小根堆 
	q.push({0, 1});			//1 到 1边权值为 0 
	d[1] = 0;
	while(!q.empty())
	{
		int x = q.top().second;		//终点 
		q.pop();		
		if(v[x])	continue;	//访问过的点不在加入 
		v[x] = 1;
		for(int i = head[x]; i ; i = Next[i])		//通过边的序号进行遍历，y为终点，z为边权值 
		{
			int y = ver[i], z = edge[i];
			if(d[y] > d[x] + z)				//如果不满足三角形定则，则进行更新
			{
				d[y] = d[x] + edge[i];
				q.push({-d[y], y});		//取-变小根堆，边权值，终点 
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i ++ )
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z);			//无向图双向加入 
		add(y, x, z);
	}	
	dijkstra();
	for(int i = 1; i <= n; i ++ )		//输出每个顶点最短距离 
		cout << d[i] << endl;
	return 0;
}

floyd

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
// Floyd算法，(n^3)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int d[310][310];
int n, m;

int main() 
{
	cin >> n >> m;
	// 把d数组初始化为邻接矩阵
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++) d[i][i] = 0;
	for (int i = 1; i <= m; i++) 
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x][y] = min(d[x][y], z);
	}
	// floyd求任意两点间最短路径
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) 
			//三角形定则更新，从1 -> n最近，则推 1 -> 2 -> 3 -> ... -> n每一步都最近，最优子结构问题，dp
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	// 输出
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) printf("%d ", d[i][j]);
		puts("");
	}
}

SPFA

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
//SPFA算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], Next[M], d[N];
int n, m, tot;
queue<int> q;
bool v[N];

void add(int x, int y, int z) 
{
	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void spfa() 
{
	memset(d, 0x3f, sizeof(d)); // dist数组
	memset(v, 0, sizeof(v)); // 是否在队列中
	d[1] = 0; v[1] = 1;
	q.push(1);
	while (q.size()) 
	{
		// 取出队头
		int x = q.front(); q.pop();
		v[x] = 0;
		// 扫描所有出边
		for (int i = head[x]; i; i = Next[i]) 
		{
			int y = ver[i], z = edge[i];
			if (d[y] > d[x] + z) 
			{
				// 更新，把新的二元组插入堆
				d[y] = d[x] + z;
				if (!v[y]) q.push(y), v[y] = 1;
			}
		}
	}
}

int main() 
{
	cin >> n >> m;
	// 构建邻接表
	for (int i = 1; i <= m; i++) 
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	// 求单源最短路径
	spfa();
	for (int i = 1; i <= n; i++)
		printf("%d\n", d[i]);
}
0%