单源最短路——Dijkstra模板-白红宇

单源最短路——Dijkstra模板

阅读量：5169 次

发布时间：2019-06-13

本文共 2891 字，大约阅读时间需要 9 分钟。

算法思想：

　　类似最小生成树的贪心算法，从起点 v₀每次新拓展一个距离最小的点，再以这个点为中间点，更新起点到其他点的距离。

算法实现：

　　需要定义两个一维数组：①vis[ i ] 表示是否从源点到顶点 i 的最短距离。②用d[ i ] 记录源点v₀到顶点 i 的距离值。

　　具体步骤如下：

　　（1）初始化 d[ v₀ ] = 0 ,源点v₀到其他点的距离值 d[ i ] = ∞ 。

　　（2）经过 n 次如下操作，最后得到 v₀ 到 n 个顶点的最短距离：

　　 ①选择一个未标记的点 v 并且 d[ v ] 的值是最小的；

　　 ②标记点 v ,即 vis[ v ] = 1；

　　 ③以 k 为中间点，修改源点 v₀到其他为标记的点 j 的距离值 d[ j ]。

算法复杂度：

　　朴素版的复杂度为 O(n²)，因为每次查找未标记的节点需耗时 O(n)，堆优化后的Dijkstra的复杂度可以降为 O( (n+m) log m )。

算法模板：

①朴素的Dijkstra

#include
     
      using namespace std;struct Edge//前向星存边{    int to;//此边的子节点    int w;//此边的权值    int next;//与它最近的父节点一样的边的编号}edge[1000000];int head[20000];//以某点为父节点引出的最后一条边int cnt=0;//边编号inline void add(int x,int y,int w)//存边{    cnt++;    edge[cnt].to=y;    edge[cnt].w=w;    edge[cnt].next=head[x];    head[x]=cnt;//更新head}int main(){    bool visit[20000]={
    0};//是否作为过起点    long long dis[20000];//距离    int n,m,s;    int x,y,w;    scanf("%d%d%d",&n,&m,&s);    for(int i=1;i<=n;i++)dis[i]=2147483647;    for(int i=0;i
      
       dis[curr]+edge[i].w)            dis[edge[i].to]=dis[curr]+edge[i].w;//更新操作        }        minn=2147483647;        for(int i=1;i<=n;i++)        {            if(!visit[i]&&minn>dis[i])//取新的最小值            {                minn=dis[i];                curr=i;            }        }//    }    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);    return 0;}

②堆优化的Dijkstra

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   using namespace std;#define maxn 100010priority_queue
                   
                    
                     ,vector
                     
                      
                        >,greater
                       
                        
                          > >q;//定义一个小根堆（优先队列） int n,m,cnt,w;int head[maxn],d[maxn],vis[maxn];//d数组表示点i和起点之间的距离，vis记录点i是否已确定，head是前向星存边~inline int read(){ char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); int xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs;}//快读struct hh{ int nex; int to; int dis;}t[maxn<<1];//前向星!inline void add(int nex,int to,int dis){ t[++cnt].to=to; t[cnt].dis=dis; t[cnt].nex=head[nex]; head[nex]=cnt;}//存边！inline void dijkstra(int w){ memset(d,0x3f3f3f3f,sizeof(d));//初始化 memset(vis,0,sizeof(vis)); q.push(make_pair(0,w));//起点入队（堆）了 d[w]=0;//自己到自己，距离0 while(!q.empty())//队（堆）不是空的，此时距离起点最小的 点在队首（堆顶） { int u=q.top().second;//u:找到了！就是这个点！ q.pop();//出队（堆），去履行更新其他点的光荣义务 if(vis[u]) continue;//如果这是一个已经确定过的点 ，跳过 vis[u]=1; for(int v=head[u];v;v=t[v].nex)//遍历一遍这个点连向的点，更新最短路 { if(d[t[v].to]>d[u]+t[v].dis&&!vis[t[v].to]) { d[t[v].to]=d[u]+t[v].dis; q.push(make_pair(d[t[v].to],t[v].to));//被更新了，进去 } } } }int main(){ int xx,yy,ww; n=read();m=read();w=read(); for(int i=1;i<=m;i++) { xx=read();yy=read();ww=read(); add(xx,yy,ww);//有向图 } dijkstra(w); for(int i=1;i<=n;i++) { printf("%d ",d[i]); }//输出return 0;}

巩固：

　　①

　　②

转载于:https://www.cnblogs.com/lck-lck/p/9614614.html

你可能感兴趣的文章