众所周知,Dijkstra算法是一个十分有效且常用的算法. 既然说了,
有效且常用
那我们就有课学习的必要了呀!
话不多说,开始讲解.
概念
1.是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止
2.Dijkstra 用来解决边权全为正(不能为负! ! ! ! ! ! )的单源最短路问题，Dijkstra算法又分为朴素Dijkstra算法和堆优化的Dijkstra算法。朴素版的Dijkstra算法的时间复杂度是O(n²),适合于稠密图，堆优化版的Dijkstra算法的时间复杂度是O(mlogn)，适合于稀疏图。
——————————————分界线————————————————
代码讲解
#define MOD 10000000007
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2000005;
int n,m,s;
int idx=1,e[maxn],w[maxn],head[maxn],ne[maxn];
int dis[maxn],vis[maxn];
MOD和INF不做过多解释,重点看e,w,head和ne数组
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=head[a];
head[a]=idx++;
}
这是一个简单的链式前向星,虽然有些奇怪的东西.
a是该点的位置,b是与该点相连的一点的位置,c则是边全
权. 我们可以看到,e数组存储了一个点到另一个点的的终点,w存储了这两个点中边的边权,ne和head数组则是普通的链式前向星啦!
恭喜你,已经学会一半了,加油!
我们再来看一组代码
struct Node
{
int dis,x;
bool operator<(Node p)const{return dis>p.dis;}
Node(int dis,int x):dis(dis),x(x){}
};
我们使用重载运算符 operator 重新定义“<”符号来对边权进行排序,方便我们接下来的操作. 下面的一行可有可无,主要是装
void dijstra()
{
memset(dis,INF,sizeof(dis));
priority_queue<Node>q;
dis[s]=0;
Node u(dis[s],s);
q.push(u);
while(!q.empty())
{
Node u=q.top();
q.pop();
if(vis[u.x])continue;
vis[u.x]=1;
for(int i=head[u.x];i!=-1;i=ne[i])
{
if(dis[e[i]]>dis[u.x]+w[i])
{
dis[e[i]]=dis[u.x]+w[i];
Node v(dis[e[i]],e[i]);
q.push(v);
}
}
}
}
这就是程序的主题了!
首先定义大根堆 priority_queue ,方便我们接下来的操作,其次,我们从s点出发,那距离s点的最短距离肯定是0,这就是 dis[s]=0的原因.
跟图有关,那我们就得使出万能且高效的
BFS!!!
如你所见,一个BFS遍历
while循环的前四行为基操,不做过多讲述,我们来看for循环
for(int i=head[u.x],i!=-1;i=ne[i])
从第x个点的链下标出发,向下一个点,也就是ne[i]前进,但由于我们标记了每一个点初始值为-1,所以还得判断一下
if(dis[e[i]]>dis[u.x]+w[i])
{
dis[e[i]]=dis[u.x]+w[i];
Node v(dis[e[i]],e[i]);
q.push(v);
}
这里我们做出判断,如果新路径的边权总和小于原路径边权总和,就改变最佳路经
圆满结束
这里附上完整代码:
#include<bits/stdc++.h>
#define MOD 10000000007
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2000005;
int n,m,s;
int idx=1,e[maxn],w[maxn],head[maxn],ne[maxn];
int dis[maxn],vis[maxn];
struct Node
{
int dis,x;
bool operator<(Node p)const{return dis>p.dis;}
Node(int dis,int x):dis(dis),x(x){}
};
inline int read()
{
int date=0,w=1;
char c;
c=getchar();
while(c<'0' || c>'9')
{
if(c=='-')w=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
date=date*10+(c-'0');
c=getchar();
}
return date*w;
}
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=head[a];
head[a]=idx++;
}
void dijstra()
{
memset(dis,INF,sizeof(dis));
priority_queue<Node>q;
dis[s]=0;
Node u(dis[s],s);
q.push(u);
while(!q.empty())
{
Node u=q.top();
q.pop();
if(vis[u.x])continue;
vis[u.x]=1;
for(int i=head[u.x];i!=-1;i=ne[i])
{
if(dis[e[i]]>dis[u.x]+w[i])
{
dis[e[i]]=dis[u.x]+w[i];
Node v(dis[e[i]],e[i]);
q.push(v);
}
}
}
}
signed main()
{
memset(head,-1,sizeof(head));
n=read(),m=read(),s=read();
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),c=read();
add(a,b,c);
}
dijstra();
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
友情提醒:本人为 ju ruo ,若觉得本文不够清晰的话,建议去寻找其他资源