图论:最短路-Dijkstra
2024-10-19 09:37:44
Dijkstra+堆优化具有稳定的时间复杂度,在一些数据范围要求比较严格(准确来说是图比较苛刻)的时候能够保证稳定的时间复杂度
但是Dijkstra不能够解决负边权的问题,所以在使用的时候一定要仔细读题
如果题目说了边权非负,首选Dijkstra算法, 如果图不是一些特殊的数据,可以尝试SPFA算法,毕竟在稀疏图面前,SPFA有着绝对的优势
Dijkstra和Prim很相似,它们的区别主要是d的含义,前者是到s的临时最短距离,后者是到树的临时最短距离,相同点是,每次找d最小的更新其它点的距离
然后,我们开始介绍用法:
int s,n,m,cnt;
int g[maxn],d[maxn];
struct Edge{int u,t,w,next;}e[maxm];
struct HeapNode{int d,u;bool operator <(const HeapNode& x) const{return d>x.d;}};
priority_queue<HeapNode> q;
在Bellman-Ford中相同的字眼我们不介绍,意义一致
HeapNode结构体和优先队列用来实现一个最小堆,堆元素是点,记录了节点号和距离值
void dijkstra(int s)
{
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
HeapNode p;
p.d=;p.u=s;q.push(p);
while(!q.empty())
{
HeapNode x=q.top(); q.pop();
int u=x.u;
if(x.d!=d[u]) continue;
for(int tmp=g[u];tmp;tmp=e[tmp].next)
if(d[e[tmp].t]>d[u]+e[tmp].w)
{
d[e[tmp].t]=d[u]+e[tmp].w;
p.d=d[e[tmp].t];p.u=e[tmp].t;q.push(p);
}
}
}
如果你能够写明白邻接矩阵的Dijkstra算法,这里具有完全一致的意义,只不过用最小堆来找距离当前点集距离最小的点,把一遍遍历变成了Log级别的
然后这里的Dijkstra算法如果用邻接矩阵的话,就是被打回原形了,所以一定要用邻接表或者邻接数组来存储
下面给出完整实现:
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x7fffffff;
const int maxn=;
const int maxm=;
int s,n,m,cnt;
int g[maxn],d[maxn];
struct Edge{int u,t,w,next;}e[maxm];
struct HeapNode{int d,u;bool operator <(const HeapNode& x) const{return d>x.d;}};
priority_queue<HeapNode> q;
void addedge(int x,int y,int z)
{
cnt++;e[cnt].u=x;e[cnt].t=y;e[cnt].w=z;
e[cnt].next=g[x];g[x]=cnt;
}
void dijkstra(int s)
{
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
HeapNode p;
p.d=;p.u=s;q.push(p);
while(!q.empty())
{
HeapNode x=q.top(); q.pop();
int u=x.u;
if(x.d!=d[u]) continue;
for(int tmp=g[u];tmp;tmp=e[tmp].next)
if(d[e[tmp].t]>d[u]+e[tmp].w)
{
d[e[tmp].t]=d[u]+e[tmp].w;
p.d=d[e[tmp].t];p.u=e[tmp].t;q.push(p);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
int x,y,z;
for(int i=;i<=m;i++) {scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);}
dijkstra(s);
for(int i=;i<=n;i++) {printf("%d ",d[i]);}
return ;
}
最新文章
- bzoj 2434 阿狸的打字机 fail树的性质
- C#:额外知识点
- Double 数据保留两位小数二:直接截取小数后面两位,不进行四舍五入
- 那些你不知道的chrome URLs
- c++ 指针常量,常量指针
- vim操作命令-笔记
- android实现透明和半透明效果
- [置顶] JUnit入门教程(二)
- 总结一下最近用过的phpcms语法
- 《Github入门与实践》读书笔记 蟲咋先生的追求之旅(上)
- C语言的隐式类型转换
- 几个常用内核函数(《Windows内核情景分析》)
- P3954 成绩(noip2017普及组)
- C#.NET常见问题(FAQ)-如何判断某个字符是否为汉字
- linux内核编译错误集锦
- Paper格式-国际会议版
- 理解活在Iphone中的那些App (二)
- 三、为什么String在Java中是不可更改的
- slot的使用实例
- centos6.5修改root密码