网络最短路算法实现(单源/全源)



  • 单源最短路

    //dijkstra算法+配对堆优化计算单源最短路
    #include<stdio.h>
    #include<stdbool.h>
    struct node{
    	struct node *fa,*l,*r;
    	int data,p;
    }buf[1000000];int ind=-1;
    struct node* root;
    struct node* _merge(struct node* u,struct node* v){
    	(v->r=u->l)?v->r->fa=v:0;
    	return u->l=v,v->fa=u;
    }
    #define merge(u,v) (u->data<v->data?_merge(u,v):_merge(v,u))
    struct node* combine(struct node* rt){
    	if(rt->r==0)return rt;
    	static struct node* arr[100000];int j=-1;
    	for(;rt!=0;rt=rt->r)arr[++j]=rt,rt->fa->r=0;
    	for(int i=0;i<j;i+=2)arr[i]=merge(arr[i],arr[i|1]);
    	for(j&1!=0?j^=1:0;j>0;j-=2)arr[j-2]=merge(arr[j-2],arr[j]);
    	return arr[0];
    }
    struct node* push(int x,int p){
    	struct node* t=&buf[++ind];t->data=x;t->p=p;
    	return root=root==0?t:merge(root,t),t;
    }
    void pop(){
        root=root->l!=0?combine(root->l):0;
    }
    void dec(struct node* p,int k){
    	p->data=k;
    	if(p==root)return;
    	if(p->r!=0)p->r->fa=p->fa;
    	if(p->fa->l==p)p->fa->l=p->r;
    	else p->fa->r=p->r;
    	p->r=0;
    	root=merge(root,p);
    }
    typedef int arr[10000];
    typedef int ard[100000];
    arr head,dis;bool vis[10000];
    ard to,next,w;
    struct node* hp[10000];
    void ae(int u,int v,int ww){
    	static int ind=1;
    	to[++ind]=v;w[ind]=ww;next[ind]=head[u];head[u]=ind;
    	to[++ind]=u;w[ind]=ww;next[ind]=head[v];head[v]=ind;
    }
    int n,m,s,t;
    void dijkstra(int s){
    	for(int i=1;i<=n;i++)dis[i]=1e9;dis[s]=0;
    	for(int i=1;i<=n;i++)hp[i]=push(dis[i],i);
    	while(root){
    		int v=root->p;pop();
    		if(vis[v])continue;vis[v]=1;
    		for(int i=head[v];i;i=next[i])
    		if(dis[to[i]]>dis[v]+w[i]){
    			dis[to[i]]=dis[v]+w[i];
    			dec(hp[to[i]],dis[to[i]]);
    		}
    	}
    }
    int main(){
    	int u,v,ww;
        scanf("%d%d%d%d",&n,&m,&s,&t);//共n个点,m条边,计算从编号s到编号t点间最短路
    	for(int i=0;i<m;++i){
            scanf("%d%d%d",&u,&v,&ww);//编号u,编号v点间有一条长度ww的路
            ae(u,v,ww);
        }
    	dijkstra(s);
    	printf("%d",dis[t]);
        return 0;
    }
    
    


  • 全源最短路

    //Floyd全源最短路
    #include<stdio.h>
    int a[100][100];
    int main(){
    	int n,m;
    	scanf("%d%d",&n,&m);//共n个点,m条边
    	for(int i=1;i<=n;++i)
    		for(int j=1;j<=n;++j)
    			a[i][j]=100000007;
    	for(int i=0;i<m;++i){
    		int u,v,w;
    		scanf("%d%d%d",&u,&v,&w);//编号u,编号v点间有一条长度ww的路
    		a[u][v]=a[v][u]=w;
    	}
    	for(int k=1;k<=n;++k)
    		for(int i=1;i<=n;++i)
    			for(int j=1;j<=n;++j)
    				if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];
    	for(int i=1;i<n;++i)
    		for(int j=i+1;j<=n;++j)
    			printf("%d-->%d: %d\n",i,j,a[i][j]);
    	return 0;
    }
    

 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待