dijkstra算法及其优化
dijkstra算法
算法概要
dijkstra算法与prim有些类似，都可以分为三个步骤，即：update、scan、add，⽤⼀个数组dis记录起点到其他节点的最短距离。从⼀个节点出发，先扫⼀遍他连的所有边，取最⼩值更新dis数组，这是update；接着扫⼀遍dis数组，找到最⼩的那⼀个，也就是从起点出发的⼀条路径，这就是scan操作；最后将找到的节点加⼊到找好的节点集合中。
简单实现
⽤这道题测试⼀下程序
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN =1e3+100;
int edge[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];
const int INF =0x3f3f3f3f;
void dijkstra(int s,int n){
memt(dis,0x3f,sizeof dis);
for(int i=1;i<=n;i++){
if(edge[s][i]!= INF) dis[i]= edge[s][i];
}vis[s]=1;
for(int i=2;i<=n;i++){
int MAX = INF;
int k=-1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]< MAX){
MAX = dis[j];
k = j;
}
}
if(k ==-1)break;
vis[k]=1;
for(int j=1;j<=n;j++){
if(!vis[j]&& edge[k][j]+ dis[k]< dis[j]&&edge[k][j]!= INF){ dis[j]= edge[k][j]+ dis[k];
}
}
}
}
int main(){
int n,m,s;
int u,v;
int w;
scanf("%d%d%d",&n,&m,&s);
memt(edge,0x3f,sizeof edge);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
edge[u][v]=min(edge[u][v], w);
}dijkstra(s, n);
dis[s]=0;
for(int i=1;i<=n;i++){
if(dis[i]== INF)printf("2147483647 ");
el printf("%d ",dis[i]);
}
return0;
}
43
可以看到除了⼏个RE，其他都没问题，RE的原因是这⾥⾯n是10的，我数组只有10，如果加⼤，会出现MLE，内存超限，虽然在本地能开到四五亿，但是显然不能符合题⽬要求，但是如果不是为了做算法题这种朴素的⽅法⼤概也可以达到⽬的。
算法优化
现在我们的问题是数组⽆法开得那么⼤，也就是说⽤邻接矩阵存储不合理，因为我们知道邻接矩阵是⽐较费空间的，尤其是在图的顶点个数⾮常多的时候，那么我们怎么办呢？因为⼀般情况下，图的存储⽅式有两种，⼀个是邻接矩阵，另外⼀个就是邻接表，所以可以考虑使⽤邻接表来存储。
再看时间上的问题，朴素的程序之中有两个地⽅很费时间，其⼀是找dis数组中最⼩值的过程，这是O（n）的，需要⼀个⼀个找，必须扫完⼀圈才能得到结果；其⼆是找这个顶点和哪些顶点之间有边，做了很多⽆⽤功，所以需要考虑如何能减少冗余操作，直⼊主题，对于第⼀个问题，我们可以⽤STL中的优先队列来解决，调整堆的时间复杂度是O（logn），这样时间上的改进是显著的；对于第⼆个问题，我们引⼊⼀种新的邻接表-链式前向星，可以解决超⼤规模图的存储问题
链式前向星
⼀般使⽤结构体存储链式前向星
下⾯是⼀般链式前向星的框架
struct Edge{
int next;//此边的下⼀条边
int to;//下⼀个节点
ll value;//边权
}edge[MAXN];
int cnt =0;//第⼏条边
void Add_Edge(int u,int v, ll value){
edge[cnt].to = v;//边的终点
edge[cnt].value = value;//边权
edge[cnt].next = head[u];//下⼀条边
head[u]= cnt++;//给边标号
}
结构体Edge⽤来存边，设u为起点，调⽤⽅法如下
for(int i=head[u];i!=-1;i=edge[i].next)
⼀般head数组赋初值为-1,
能够看出调⽤的时候是反着取边的，也就是最后输⼊的边先调⽤，但是不影响最短路
使⽤链式前向星改进模板题的朴素dijstra如下
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN =2e6+100;
int head[MAXN];
int vis[MAXN];
ll dis[MAXN];
int cnt;
struct Edge{
int to;
int next;
ll value;
}edge[MAXN];
void Add_edge(int u,int v, ll value){
edge[cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].value = value;
head[u]= cnt++;
}
void init(int n){
for(int i=0;i<=n;i++) dis[i]=2147483647;
memt(head,-1,sizeof head);
memt(vis,0,sizeof vis);
cnt =0;
}
void dijkstra(int s,int n){
vis[s]=1;
for(int i=head[s];i!=-1;i=edge[i].next){
if(dis[edge[i].to]> edge[i].value) dis[edge[i].to]= edge[i].value; }//这个位置要注意
for(int i=1;i<n;i++){
ll MAX =2147483647;
int k =-1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]< MAX){
MAX = dis[j];
k = j;
}
}
if(k ==-1)break;
vis[k]=1;
for(int j=head[k];j!=-1;j=edge[j].next){
if(!vis[edge[j].to]&&dis[k]+ edge[j].value < dis[edge[j].to]){ dis[edge[j].to]= dis[k]+ edge[j].value;
}
}
}
}
int main(){
int n,m,s,u,v;
ll w;
scanf("%d%d%d",&n,&m,&s);
init(n);
for(int i=0;i<m;i++){
scanf("%d%d%lld",&u,&v,&w);
Add_edge(u, v, w);
}
dijkstra(s, n);
dis[s]=0;
for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
return0;
}
这样可以通过这道题，紧接着我们尝试这道题
⽤上述程序，得到所有测试点均为TLE，这样，我们尝试继续优化
堆优化
还剩下⼀个优化点，就是查找最短边的scan步骤，这让⼈联想到⼩顶堆，每次需要调整堆顶元素为最⼩，那么我们使⽤STL中的优先队列就会很⽅便，注意需要重载<
得到最终程序
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const ll INF =2147483647;
const int MAXN =2e6+100;
int head[MAXN];
int vis[MAXN];
int cnt;
ll dis[MAXN];
struct T{
int id;
int dis;
bool operator<(const T &a)const{
return a.dis < dis;
}
};
struct Edge{
int next;
int to;
ll value;
}edge[MAXN];
void init(int n){
memt(head,-1,sizeof head);
for(int i=0;i<=n;i++) dis[i]= INF;
cnt =0;
}
void Add_Edge(int u,int v, ll value){
edge[cnt].to = v;
edge[cnt].value = value;
edge[cnt].next = head[u];
head[u]= cnt++;
}
void dijkstra(int s){
priority_queue<T> q;
dis[s]=0;
T now;
now.dis = dis[s];
now.id = s;
q.push(now);
while(!q.empty()){
T u = q.top();
q.pop();
