hdu 2544 dijkstra模板

缘起

学了dijkstra这么重要的算法（这可是拿图灵奖的算法），怎么能没有一块趁手的板子呢? 遂找到 hdu 2544 最短路 来学习一下.

分析

题目是中文的.

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
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运
回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ 


【输入】
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的
路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3
个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这
条路。 输入保证至少存在1条商店到赛场的路线。 

【输出】
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

【样例输入】
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

【样例输出】
3
2

【限制】
Time limit 1000 ms 
Memory limit 32768 kB

【来源】
UESTC 6th Programming Contest Online

本题是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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
typedef pair<int, int> P;
//#define LOCAL

const int maxn = 105, maxm = 20005;
int n,m, head[maxn], cnt,d[maxn]; // cnt是弧的数量

struct Arc
{
	int from, to, nxt, len; // 一条从from到to的弧, 长度为len, nxt是从from出发的下一条弧
	Arc(){}
	Arc(int from, int to,int nxt, int len):from(from),to(to), nxt(nxt),len(len){}
}g[maxm]; // g是弧的数组

void addarc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]=cnt++; // 头插入g[cnt]这条弧到head[a]去
	g[cnt] = Arc(b,a,head[b], c);
	head[b] = cnt++;
}

int dijkstra()
{
	priority_queue<P, vector<P>, greater<P> > pq; // 小根堆(P的first是距离, 越小, 优先级越大, second是顶点标号)
	pq.push(P(0,1));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		int h = top.second; // 得到此次用于松弛各最短距离的顶点
		for (int x = head[h]; ~x; x = g[x].nxt) // x是弧的编号, 这里是在遍历所有从x出发的弧
		{
			int to = g[x].to; // g[x].from = h
			if (d[to]>g[x].len+d[h]) // 用g[x]这条从h出发,终于to的弧尝试松弛d[to]
			{
				d[to] = g[x].len+d[h];
				pq.push(P(d[to],to));
			}
		}
	}
	return d[n];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		memset(d, 0x3f, sizeof(d));
		d[1] = 0;
		while (m--)
		{
			int a,b,c;
			scanf("%d%d%d", &a, &b, &c);
			addarc(a,b,c);
		}
		printf("%d\n", dijkstra());
	}
	return 0;
}

ac情况（C++提交编译会报错, 需要以G++提交）

Status Accepted
Time 15ms
Memory 1348kB
Length 1374
Lang G++
Submitted 2019-08-22 10:23:00
Shared
RemoteRunId 30384976

这里需要解释一下上面的dijkstra算法. 这是网上流传比较多的板子. 和之前我用的那种有 inU数组的不一样. 因为流程是每次pop出最短的，然后使用这个最短的距离尝试松弛各个顶点到单源的距离. 注意，dijkstra算法其实也是基于dp的思想，因为你想啊，每个顶点u到单源1的最短距离肯定有一个前置顶点v（v可能就是单源1）吧? 即u的前一步是v. 那么可以断言1到v的距离一定是最短的. 不然的话, 可以松弛1到v的距离来达到到达u的更短距离. 只是未必是DAG，所以你不知道从哪个顶点开始求起. 所以DAG图的单源最短路径算法是更简单的.

回到正题，为什么不需要每次将上一轮已经在pq中的元素全部pop出来再将本轮松弛的结果push进去? 因为前一轮push进去的根本没机会pop出来. 因为本轮就是在上一轮的基础上push进去的. 所以上一轮push进去的结果不可能成为本轮最小的pop出来. 所以可以这么搞.

更快的板子

其实看看上面的板子, 如果和之前O(n^2)朴素的dijkstra算法比较, 就感觉上面的板子有点冗余——比如一个点已经曾经作为堆的top出来过. 现在又出来了, 则它还需要去松弛其他弧吗? 显然是不需要的. 可以直接continue掉.

典型例子可以参见下图

(5,4)即4距离单源路径为5肯定进入过堆（事实上, 第一轮扫描就进入了堆），所以一定有出堆的时候（因为最后要堆空的），但是（4,4） 也进入过堆（由3去松弛3->4 这条从3出发的弧），而且（4,4）在(5,4)之前出堆（因为4<5）, 那么等到(5,4)出堆的时候显然不需要再用5去松弛其他从4出发的弧，也就是(5,4)出堆之后, 直接continue掉就好了. 究其根本是因为4既然已经作为堆顶元素出过堆, 所以它已经达到单源最短了. 后面出堆的(5,4)的5一定不是到4的最短路. 那你用5去松弛从4出发的弧有何意义呢? 因为我已经用4去松弛过从4出发的弧了（(4,4)出堆的时候）. 其次, 在松弛其他弧的时候, 对于已经达到最短路的点不需要去松弛（即已经出过堆的点），例如上图中出堆的(3,2)不需要去松弛已经出堆的3，因为3已经达到最短路2了（如果存在还能真正意义上松弛（即真的能减小距离）已经出堆的点的话, 例如当前出堆的(A,B) 还能真正松弛已经出堆的(C,D),即A+|B-D|<C, 这里严格< 就体现”真正”二字. 则因为非负权（所以对于dijkstra而言,非负权这个条件是本质的）, 则A<C, 那么根据算法使用小根堆, 怎么会(A,B)在(C,D)后面才出堆呢? 矛盾! 所以不可能在一个点出堆之后还发生真正意义上松弛,但是A+|B-D|==C 即非严格的松弛是可能的发生的，但是非严格意义上的松弛的发生并不会影响最短路长度的最后计算值. 所以完全可以不理会。综上2点，我们可以得到更快的dijkstra的板子（或者说和朴素O(n^2)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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
typedef pair<int, int> P;
//#define LOCAL

const int maxn = 105, maxm = 20005;
int n,m, head[maxn], cnt,d[maxn];
bool v[maxn];
struct Arc
{
	int from, to, nxt, len; 
	Arc(){}
	Arc(int from, int to,int nxt, int len):from(from),to(to), nxt(nxt),len(len){}
}g[maxm]; 

void addarc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a], c);
	head[a]=cnt++; 
	g[cnt] = Arc(b,a,head[b], c);
	head[b] = cnt++;
}

int dijkstra()
{
	memset(v,0,sizeof(v));
	priority_queue<P, vector<P>, greater<P> > pq; 
	pq.push(P(0,1));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		int h = top.second; 
		if (v[h])
		{
			continue; // 对于已经出过堆（即达到最短路径的）点, top->first肯定>=h的单源最短,所以不需要再用h去松弛从h出发的其他弧了
		}
		v[h] = true;
		for (int x = head[h]; ~x; x = g[x].nxt)
		{
			int to = g[x].to; 
			if (!v[to] && d[to]>g[x].len+d[h]) // 对于已经到达最短路径的to,也不需要去松弛了
			{
				d[to] = g[x].len+d[h];
				pq.push(P(d[to],to));
			}
		}
	}
	return d[n];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		memset(d, 0x3f, sizeof(d));
		d[1] = 0;
		while (m--)
		{
			int a,b,c;
			scanf("%d%d%d", &a, &b, &c);
			addarc(a,b,c);
		}
		printf("%d\n", dijkstra());
	}
	return 0;
}

ac情况（0ms）

Status Accepted
Memory 1352kB
Length 1382
Lang G++
Submitted 2019-10-28 16:18:52
Shared
RemoteRunId 31149262

所以如果有人现在再问我——dijkstra为什么能保证算法正确? 我会告诉TA

因为dijkstra算法保证了已经出堆的元素后续不可能发生严格意义上的松弛（但是非严格意义上的松弛还是可能发生的）, 证明见上面的反证法. 其中体现了dijkstra算法对于非负权条件本质的依赖. 所以对于负权图, dijkstra算法是不正确的.

特别地, 如果是正权（有向）图, 则所有的松弛都是严格意义上的松弛, 所以对于正权（有向）图，dijkstra算法保证了已经出堆的元素后续甚至不可能发生非严格意义上的松弛.

因为一旦已经出堆就不可能被严格意义上松弛, 所以dijkstra算法一定在有限步结束, 而且对于含圈的非负权（有向）图也是适用的（因为上面的分析并没有用到”此图必须无圈”这种条件）.