简单的图论问题之单源最短路dijkstra算法
Solution: Dijkstra (大概读作:迪杰斯特拉?)
算法思想:
给定一张n个点,m条边的图,起点为s。求起点s到图中所有点的最短路径(单源最短路。dis[i]表示从起点到i的最短距离。vis[i]表示此点是否已被标记确定为最短。
1、初始化dis[s]=0,其余结点dis为正无穷大。
2、找到一个未被标记的、dis[x]最小的结点x,标记x。
3、扫描结点x的所有出边(x,y,z),若dis[y]>dis[x]+z,则用dis[x]+z更新dis[y]。
4、重复2、3步骤,知道所有点均被标记。
复杂度:O(n^2)。
优化:优先队列(堆)。
?```#include <queue>``` ?```priority_queue< pair<int,int> >q;```
https://www.luogu.com.cn/problem/P4779
对dis数组进行维护,加快获取最小值以及执行一条边的扩展与更新。
代码:
#include <cstdio> #include <queue> #include <cstring> using namespace std; typedef long long int ll; const int maxn=1000005; ll n,m,s,tot,head[maxn],x,dis[maxn]; priority_queue< pair<ll,ll> >q;//优先队列(二叉堆)两维:第一维为dis[i]相反数第二维结点编号 struct node{ ll nxt,to; ll w; }t[maxn];//链式前向星存图 void add(const int u,const int v,const int w){ t[++tot].to=v;t[tot].w=w; t[tot].nxt=head[u];head[u]=tot; }//加边 bool vis[maxn]; void dijkstra(){ memset(dis,0x3f,sizeof(dis));//初始边无限大 memset(vis,0,sizeof(vis));//结点初始均为访问 dis[s]=0;//起点到自己距离为零 q.push(make_pair(0,s));//起点进堆 while(q.size()!=0){// x=q.top().second;q.pop();//初始结点入队 if(vis[x])continue;//如果走过,直接跳过 vis[x]=1;//标记已访问 for(ll i=head[x];i;i=t[i].nxt){ ll y=t[i].to,z=t[i].w; if(dis[y]>dis[x]+z){//松弛 dis[y]=dis[x]+z;//更新起点到y最短路 q.push(make_pair(-dis[y],y));//d[y]相反数入队,转小根堆。 } } } } int main(){ scanf("%lld%lld%lld",&n,&m,&s);//n个点,m条边,起点为s。 for(int i=1;i<=m;i++){ ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c); add(a,b,c); } dijkstra(); for(int i=1;i<=n;i++){ printf("%lld ",dis[i]); } }
相关推荐
Happyunlimited 2019-11-01
ResysChina 2018-04-22
ResysChina 2018-04-14
MATLAB 2018-04-12
锦妖和她的小伙伴们 2018-02-21