图论:单源最短路

这是一篇讲解单源最短路算法Dijkstra的文章,阅读前先了解图的数据结构(带权图,无向图,有向图)

概念:

单源最短路:

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。
要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称
为单源最短路径问题。

Dijkstra

迪杰斯特拉算法(Dijkstra),是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶
点的邻接节点，直到扩展到终点为止。

需要注意的是，dijkstra算法只能解决正权图问题。

算法原理与实现:

我们使用链式前向星存图，存储每一条边，以edge数组作为容器
edge的下标是cnt，而不是节点名称，cnt作为该条边的编号，规定cnt单增，每一条新的边的编号都是当前cnt+1
edge[cnt].to的值表示这条边指向的目标点
edge[cnt].next的值是一个cnt,它指向的是下一个与起点连接的节点的cnt
如果该节点不指向任何一个节点，那么规定next 的值为-1
edge[cnt].w指的是边的权值
head数组存储每一个点存储的第一条边的编号，下标就是该点的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Edge {
public:
	int to, next, w;
}edge[Num];
int head[Num], dis[Num], cnt = 0;
bool vis[Num];
void init() {
	memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w) {
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

将所有点归类为两个点集，点集A存储还未找到最短路径的点，点集B则存储已找到最短路的点。
我们创建一个Bool类型vis数组区分每一个点在哪个点集，若为false则说明在A点集，为true则在B点集，
初始所有点的vis默认为false(bool数组的特性，在不初始化时，默认值都为false)
然后设置数组dis，表示源点到每个点距离，在初始时，我们将源点距离设置为0，并将vis设置为true，
其他所有点的距离用memset设置为0x3f(memst函数的赋值方式是逐字节的，而int类型
占4个字节，故memset会将每一个点的距离设置为0x3f3f3f3f，这是一个极大数，用来表示目前无法到达该点)。

1
2
3
4
5
int dis[Num];
bool vis[Num];
memset(dis, 0x3f, sizeof(dis));
dis[Start] = 0;
vis[Start] = true;

由于Dijkstra算法是一种贪心算法，要将当前点集B的所有边进行排序，选出终点不在点集B而且距离最短的边，
使用传统容器每次存储后需要进行排序，这种遍历行为的时间复杂度是O(N)级别，而Dijkstra算法本身就需要
进行O(N)次选点，这样下来总的时间复杂度是O(N^2)级别的，我们能否将其优化，使得将边排序的复杂度降低?
这就需要一个名为堆的数据结构了，堆是一种完全二叉树，是以自上而下升序(降序)的方式排列，插入的复杂度
是O(logN)级别，我们需要的是当前最短的边，因此选择小根堆(升序)，C++中的stl中含有一个名为优先队列(priority_queue)的容器内部实现就是堆，所以我们可以直接使用，在堆中存储对组(点的距离，点的编号)
，为了方便，我们用pii命名pair< int, int>。

1
2
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> heap;

最后便是Dijkstra算法的具体实现，基本原理就是每次存入一个距离源点最短的点，将距离和编号放入堆，然后
查询放入点后源点能到达所有点中，距离最短的点，重复操作，直至所有点都进入点集B，则算法完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dijkstra(int Start) {
	heap.emplace(dis[Start], Start);
	while(heap.empty()==0) {
		auto now = heap.top();
		if (vis[now.second]){
			heap.pop();
			continue;
		}
		vis[now.second] = true;
		heap.pop();
		for (int i = head[now.second]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dis[v] > edge[i].w + dis[now.second]) {
				dis[v] = edge[i].w + dis[now.second];
				heap.emplace(dis[v], v);
			}
		}
	}
}

代码总览:

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
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e+5;
class Edge {
public:
	int to, next, w;
}edge[lim+5];
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> heap;
int head[lim+5], dis[lim+5], cnt = 0;
bool vis[lim+5];
void init() {
	memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w) {
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void dijkstra(int Start) {
	memset(dis, 0x3f, sizeof(dis));
	dis[Start] = 0;
	heap.emplace(dis[Start], Start);
	while (heap.empty() == 0) {
		auto now = heap.top();
		if (vis[now.second]) {
			heap.pop();
			continue;
		}
		vis[now.second] = true;
		heap.pop();
		for (int i = head[now.second]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dis[v] > edge[i].w + dis[now.second]) {
				dis[v] = edge[i].w + dis[now.second];
				heap.emplace(dis[v], v);
			}
		}
	}
}
int main() {
	int n, m, s;
	cin >> n >> m >> s;
	init();
	int u, v, w;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> w;
		addEdge(u, v, w);
	}
	dijkstra(s);
	for (int i = 1; i <= n; i++) {
		if (i == 1)cout << dis[i];
		else cout << " " << dis[i];
	}
	return 0;
}

完结撒花