单源最短路径 dijkstra

dijkstra是单源最短路径算法，要两个数组来维护需要的信息

dis[i]用来维护起始点到i点的最短距离，初始化为一个很大的数字 0x3f3f3f3f

vis[i]用来维护是否访问过该点，初始化为0，即没有访问过

dijkstra算法有朴素版实现和优先队列优化版本

朴素版

dijkstra算法思路如下：

1、确定一个起始点begin

2、让dis[begin] = 0

3、选取一个让dis[s]最小，且没有访问过的点s（第一次访问的节点是起始点）

4、让vis[s] = 1表示已经访问过s点

5、对于与s相连的点i，比较dis[s]+s、i之间的距离和dis[i]的大小，

如果前者比较小，说明找到一条从起始点到i点更短的路，就要更新dis[i]

让dis[i] = dis[s] + s、i之间的距离。

如果前者比较大，说明没有找到一条从起始点到i点更短的路，不需要更新dis[i]

6、重复3到5的步骤直到所有节点都被访问过

7、dis数组更新完毕，当前dis[i]就表示起始点到i点的最短距离

优先队列优化版

优化的是步骤3，从原本的遍历所有点比较大小再选取最小的点，

变成了直接选优先队列的头，时间复杂度从O(n)变为O(logn)

朴素版的时间复杂度为O(n²) 优化版的时间复杂度为O(nlogn)

来一个例子

 

A、B、C、D、E、F点的编号分别为1、2、3、4、5 、6

假如要计算1号点到其他点的最短距离

1.就把1号点当作起点

2.dis[1] = 0,dis[2] = 0x3f3f3f3f,dis[3] = 0x3f3f3f3f,dis[4] = 0x3f3f3f3f,dis[5] = 0x3f3f3f3f,dis[6] = 0x3f3f3f3f

3.因为dis[1]为0所以这时候dis[1]最小，所以选1号点，vis[1] = 1表示访问过了

4.1号点选完之后，与1号点相连的点有2号 5号 6号 点

5.由于dis[2] > dis[1] + 6 所以更新dis[2]  dis[2] = dis[1] + 6

由于dis[6] > dis[6] + 1 所以更新dis[6]  dis[6] = dis[1] + 1

由于dis[5] > dis[1] + 5 所以更新dis[5]  dis[5] = dis[1] + 5

现在dis[1] = 0, dis[2] = 6, dis[3] = 0x3f3f3f3f, dis[4] = 0x3f3f3f3f, dis[5] = 5,dis[6] = 1

6.继续选下一个点，因为1号点选过了，所以应该选除了1号点之外dis最小的点，即6号点

7.与6号点相连的有1号 2号 3号 4号 5号

由于dis[2] > dis[6] + 2 所以更新dis[2] dis[2] = dis[6] + 2

由于dis[3] > dis[6] + 8 所以更新dis[3] dis[3] = dis[6] + 8

由于dis[4] > dis[6] + 4 所以更新dis[4] dis[4] = dis[6] + 4

由于dis[5] < dis[6] + 9 所以不更新

现在dis[1] = 0,dis[2] = 3, dis[3] = 9,dis[4] = 5,dis[5] = 5,dis[6] = 1

继续选没有选过的点直到所有的点都被选过

洛谷P3371 

代码 

#include 
using namespace std;
const int MAXN = 100010;
int n,m;
struct edge{
	int v,w;
};
int dis[MAXN],vis[MAXN];
void dijkstra (int begin, vector v[]){
		memset(dis,0x3f3f3f3f,sizeof(dis));
		dis[begin] = 0;
		for(int i = 1;i <= n; i++){
			int s = 0,min = 0x3f3f3f3f;
			vis[s] = 1;
			for(int j = 1;j <= n; j++){
				if(!vis[j] && dis[j] < min){
					min = dis[j];
					s = j;
				}
			}
			vis[s] = 1;
			for(auto x : v[s]){
				if(dis[x.v] > dis[s] + x.w) 
					dis[x.v] = dis[s] + x.w;
			}
		}
	};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int s,t1,t2,w;
	cin >> n >> m >> s;
	vector v[n+1];
	for(int i = 1;i <= m; i++){
		cin >> t1 >> t2 >> w;
		v[t1].push_back({t2,w});
	}
	
	dijkstra(s, v);
	for(int i = 1;i <= n; i++){
		if(dis[i] < 0x3f3f3f3f)
			cout << dis[i] << " ";
		else cout << 2147483647 << " ";
	}
}

优先队列优化版

洛谷P4779

#include 
using namespace std;
const int MAXN = 100010;
int n,m;
struct edge{
	int v,w;
};
int dis[MAXN],vis[MAXN];
struct info{
	int d,v;
	bool operator < (const info & a) const {
		return d > a.d;
	}
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int s,t1,t2,w;
	cin >> n >> m >> s;
	vector v[n+1];
	for(int i = 1;i <= m; i++){
		cin >> t1 >> t2 >> w;
		v[t1].push_back({t2,w});
	}
	function<void(int)> dijkstra = [&](int begin){
		memset(dis,0x3f3f3f3f,sizeof(dis));
		dis[begin] = 0;
		priority_queue< info > pq;
		pq.push({0,begin});
		while(!pq.empty()){
			int vi = pq.top().v;
			pq.pop();
			if(vis[vi]) continue;
			vis[vi] = 1;
			for(auto x : v[vi]){
				if(dis[x.v] > dis[vi] + x.w) {
					dis[x.v] = dis[vi] + x.w;
					pq.push({dis[x.v],x.v});
				}
			}
		}
	};
	dijkstra(s);
	for(int i = 1;i <= n; i++){
		cout << dis[i] << " ";
	}
}