微信小程序网站建设小图标素材,网站开发环境 对比,龙岩市住房和城乡建设局网站,企业网站seo外包Dijkstra算法模板
蓝桥杯中也是会考到图论最短路的#xff0c;一旦考到#xff0c;基本是不会太难的#xff0c;只要知道板子就基本能拿分了。
两个板子如下
朴素Dijkstra算法
适应情况#xff1a;稠密图#xff0c;正权边
时间复杂度 O(n^2 m)
int dijkst(){memse…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_queuePII, vectorPII,greaterPII 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];
}
