【备战蓝桥杯系列】单源最短路径Dijkstra算法模板

Dijkstra算法模板

蓝桥杯中也是会考到图论最短路的，一旦考到，基本是不会太难的，只要知道板子就基本能拿分了。

两个板子如下

朴素Dijkstra算法

适应情况：稠密图，正权边

时间复杂度 O(n^2 + m)

int dijkst(){memset(dist, 0x3f, sizeof dist);//初始化成无穷大dist[1] = 0;for(int i = 1; i <= n; i ++ ){//寻找所有点到起点的最短距离int t = -1;for(int j = 1; j <= n; j ++ ){//找到未确定且距离最小的点if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}st[t] = true;//将该点确定for(int j = 1; j <= n; j ++ ){//用该点距离更新其他点dist[j] = min(dist[j], dist[t] + g[t][j]);}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

堆优化版dijkstra

适应情况：稀疏图，正权边

时间复杂度 O(mlongn) — 堆每次更新值时间复杂度是logn，而通过邻接表来存，

​ 每次只遍历与该点相连的边，所以总的遍历次数是m，故时间复杂度是mlogn

int dijkstra(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>,greater<PII>> heap;heap.push({0, 1});while(heap.size()){//第一步遍历auto t = heap.top();//第二步①找出未确定的距离最小的点heap.pop();int dis = t.first, ver = t.second;if(st[ver]) continue;st[ver] = true;//第二步②将该最短距离确定下来for(int i = he[ver]; i != -1; i = ne[i]){//第三步 更新dist数组int j = e[i];if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];heap.push({dist[j], j});//此处会产生冗余，对于产生新的最短距离的点，其{旧值距离，点}会成为冗余数据，//下沉到堆得下半部分}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}