Dijkstra算法-求单源最短路径（2019.6.13训练）
前言
Dijkstra算法，是正权图中求单源最短路径的经典算法，其朴素算法时间复杂度为O(n2)，加入优先队列优化(堆优化)后时间复杂度可以达到O((m+n)logn)。注意Dijkstra算法不适用于负权图（负环图？？？）， 也就是说给出的边权不能有负值。正权图最好用Dijkstra算法，相较于SPFA算法比较稳定。（以上来自于洛谷大佬的总结）
为了更好地理解Dijkstra算法(优化)，需要知道链式前向星和优先队列， 如果不太清楚可以看看这两篇文章：
OK，如果你已经知道了链式前向星和优先队列，下面我们开始正式做题。
洛谷 P3371 单源最短路径（弱化版）（数据太弱，不建议做）
教科书式的Dijkstra算法模板题，以下给出教科书式的AC代码，具体思路详见注释。
#include <bits/stdc++.h>
using namespace std;
const int N=10010,M=500010;
int n,m,s,x,y,z,cnt,dis[N],vis[N],head[M];
struct node
{
int w,to,next;
}e[M];//定义边的三个信息，w表示边权，to表示边的终点，next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];//next表示以x为起点的上一条边的编号
head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
struct cmp//优先队列中的自定义排序
{
bool operator()(int x,int y)
{return dis[x]>dis[y];}//注意写大于号还是小于号与实际的符号相反，实际是小于号，则要写大于号
};
priority_queue<int,vector<int>,cmp>q;//定义一个按dis数组值从小到大排序的优先队列，存放的是dis数组的下标，为int类型
void dijkstra()
{
q.push(s);dis[s]=0;//起点入队，起点到自身距离为0
while(!q.empty())
{
int x=q.top();q.pop();
vis[x]=0;//出队标记
for(int i=head[x];i!=-1;i=e[i].next)//遍历以x为起点的所有边
{
int to=e[i].to;//to为遍历到的边的终点
if(dis[to]>dis[x]+e[i].w)
{
dis[to]=dis[x]+e[i].w;//更新最短距离
if(!vis[to])//将未入队的终点to入队并标记
{
q.push(to);
vis[to]=1;//入队标记
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>s;
memset(head,-1,sizeof(head));//head数组初始化
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
for(int i=1;i<=n;i++)//dis数组初始化
dis[i]=2147483647;
dijkstra();
for(int i=1;i<=n;i++)
i==n?printf("%d\n",dis[i]):printf("%d ",dis[i]);
return 0;
}
讨论重载运算符的写法：https://www.luogu.org/blog/53164/dijkstra-heap
洛谷 P4779 单源最短路径（标准版）
和上题同样的方法，不多说。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m,x,y,z,s,cnt,dis[N],vis[N],head[M];
struct edge
{
int w,to,next;
}e[M];
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node
{
int w,now;
bool operator < (const node &x) const//定义时的顺序不能颠倒，第一个表示dis[i]，第二个表示dis[i]中的下标i
{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
q.push({0,s});dis[s]=0;
while(!q.empty())
{
int x=q.top().now;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(dis[to]>dis[x]+e[i].w)
{
dis[to]=dis[x]+e[i].w;
q.push({dis[to],to});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
dijkstra();
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
洛谷 P1144 最短路计数
SPFA代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{
int w,to,next;
}e[M<<1];//无向图，边数乘2
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
queue<int>q;
void spfa()
{
q.push(1);dis[1]=0;ans[1]=1;//从1开始，到1自身的最短路径只有1条，最短路径长度为0
while(!q.empty())
{
int x=q.front();q.pop();
vis[x]=0;//出队标记
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(dis[to]>dis[x]+e[i].w)
{
ans[to]=ans[x];
dis[to]=dis[x]+e[i].w;
if(!vis[to])
{
vis[to]=1;//入队标记
q.push(to);
}
}
else if(dis[to]==dis[x]+e[i].w)
ans[to]=(ans[to]+ans[x])%mod;
}
}
}
int main()
{
ios::sync_with_stdio(false);
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
add(x,y,1);
add(y,x,1);//注意是无向图，输入的是一条边的信息，实际上要存储的是两条边的信息(还包括反向的)
}
spfa();
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
Dijkstra代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{
int w,to,next;
}e[M<<1];//无向图，边数乘2
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node
{
int w,now;
bool operator < (const node &x) const
{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
q.push({0,1});dis[1]=0;ans[1]=1;//从1开始，到1自身的最短路径只有1条，最短路径长度为0
while(!q.empty())
{
int x=q.top().now;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(dis[to]>dis[x]+e[i].w)
{
ans[to]=ans[x];
dis[to]=dis[x]+e[i].w;
q.push({dis[to],to});
}
else if(dis[to]==dis[x]+e[i].w)
ans[to]=(ans[to]+ans[x])%mod;
}
}
}
int main()
{
ios::sync_with_stdio(false);
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
add(x,y,1);
add(y,x,1);//注意是无向图，输入的是一条边的信息，实际上要存储的是两条边的信息(还包括反向的)
}
dijkstra();
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
洛谷 P2243 电路维修
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,t,c,cnt,x[N],y[N],z[N],dis[N],vis[N],head[N];
struct edge
{
int w,to,next;
}e[N];
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node
{
int w,now;
bool operator < (const node &x) const
{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
q.push({0,1});dis[1]=0;
while(!q.empty())
{
int x=q.top().now;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(dis[x]+e[i].w<dis[to])
{
dis[to]=dis[x]+e[i].w;
q.push({dis[to],to});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;char f;
while(t--)
{
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));cnt=0;
cin>>n>>m;c=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>f;
if(f=='/')
{
x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=0;
x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=1;
}
else
{
x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=0;
x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=1;
}
}
for(int i=1;i<=c;i++)
{
add(x[i],y[i],z[i]);
add(y[i],x[i],z[i]);//注意是双向的无向图！！！
}
dijkstra();
if(dis[(n+1)*(m+1)]==0x3f3f3f3f)printf("NO SOLUTION\n");
else printf("%d\n",dis[(n+1)*(m+1)]);
}
return 0;
}
洛谷 P1186 玛丽卡
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e6+10;
int n,m,f,x,y,z,cnt,ans,dis[N],vis[N],head[M],flag[N][N],pre[N];
struct edge
{
int w,to,next;
}e[M];
void add(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
struct node
{
int w,now;
bool operator < (const node &x) const
{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q.push({0,1});dis[1]=0;
while(!q.empty())
{
int x=q.top().now;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(flag[x][to]==0&&dis[to]>dis[x]+e[i].w)
{
if(f==0)pre[to]=x;
dis[to]=dis[x]+e[i].w;
q.push({dis[to],to});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dijkstra();
f=1;
for(int i=n;i!=1;i=pre[i])
{
flag[pre[i]][i]=1;
flag[i][pre[i]]=1;
dijkstra();
flag[pre[i]][i]=0;
flag[i][pre[i]]=0;
ans=max(ans,dis[n]);
}
printf("%d\n",ans);
return 0;
}
查看15道真题和解析
