【计算机算法设计与分析】单源最短路径问题（C++_dijkstra算法-贪心算法）

问题描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出s号点到每个点的最短距离。

测试样例

输入样例1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例1

0 2 4 3

输入样例2

3 3 1
1 2 2
2 3 1
1 3 4

输出样例2

0 2 3

算法原理

迪杰斯特拉算法过程维护两个集合S和U，S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点。由下图可以看出迪杰斯特拉算法实际上就是不断贪心地选择与起点距离最近的点，并将其从U集合中取出加入到S集合中，这个过程不断迭代，直到所有的点都被加入S。

迪杰斯特拉算法的实现就是对这个过程的模拟：

1. 最初起点到达所有点的距离都是未知的，记作无穷大。
2. 在对起点的邻接点进行扫描后发现，起点可以通过某些边抵达一些节点，那么就更新d数组（d[i]用于记录起点s到i之间的已知最短距离），并将更新后的数据（数据形式为一对数值：{距离dis，点p}，代表起点s到点p的目前已知最短距离dis）放入优先队列（一种数据结构，其实就是最小堆，会自动把距离最近的点放在堆顶，方便取用，节省了不断查找最小值的复杂度）。
3. 然后不断从优先队列中取数据（取出的点p就相当于已经加入了u集合，因为每次都贪心地取了最近的点，而已经加入u集合的点不需要再重复计算，因此引入vis数组记录该过程），然后将取出的数据中的点p作为中转站，对于图中每个点i都比较当前d数组中记录的d[i]（起点s到i之间的已知最短距离）与d[p]+g[p][i]（g[i][j]是邻接矩阵，代表i到j的距离，d[p]+g[p][i]表示从起点s到点p的距离加上从点p到点i的距离），若d[i]更大，也就意味着七点到i的距离其实并不是最短距离，那么就更新d[i]=d[p]+g[p][i]，并将更新后的数据放入优先队列。
4. 不断重复这个过程，将数据不断压入优先数列再不断贪心地取最短路径，直到队列被全部取空为止，算法结束。

算法实现

#include<bits/stdc++.h>
#define INF 0x3f
#define P pair<int, int>
using namespace std;

int d[10000], vis[10000], g[100][100];  //vis用于记录已经被走过的点
int n, m, s, cnt = 0;
priority_queue<P, vector<P>, greater<P> >a;  //堆优化

void dij() {
	memset(d, INF, sizeof d);
	d[s] = 0;  //表示除了自身之外都是不可到达的
	a.push({0,s});  //把点逐个加入优先队列，按照从小到大的顺序更新周围的点
	while (!a.empty()) {
		int p = a.top().second;
		a.pop();
		if (!vis[p]) {  //已经被采纳的点不用加入两次
			vis[p] = 1;
			for (int i = 1; i <= n; i++) { 
				if (d[i] > d[p] + g[p][i]) {
					d[i] = d[p] + g[p][i];
					a.push({d[i], i});
				}
			}
		}
	}
}

void dijkstra() {
	cin >> n >> m >> s;  //n个点，m条边，起点为s
	memset(g, INF, sizeof g);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = w;
	}
	dij();
	for (int i = 0; i < n; i++)
		cout << d[i + 1] << " ";
}

参考资料

1. Dijkstra算法图文详解
2. （迪杰斯特拉）Dijkstra算法及其优化（C++）
3. P4779 【模板】单源最短路径（标准版）（C++_Dijkstra_堆优化_链式向前星）