Java教程

最短路算法

本文主要是介绍最短路算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

被这几个板子折磨，打一打最近学的最短路模板
Floyd朴素算法
优点:全能,编程复杂度低
缺点：时空复杂度高，不易优化

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define map mymap
const int p=100+1;
int n,m,s,t;
int ans;
int map[p][p];
int main(){
    cin>>n>>m>>s>>t;
    memset(map,0x3f,sizeof(map));
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
            }
        }
    }
    cout<<map[s][t];
    return 0;
}
Dijsktra迪杰斯特拉算法

优点：时间复杂度较小，为O（n^2）级（应用数据规模从500到10000），可以被优化，复杂度稳定
缺点：无法处理负边权问题，单源
1.无优化

普通的Dijsktra算法 
#include <bits/stdc++.h>
using namespace std;
int a[101][3];
double c[101];
bool b[101];
double f[101][101];
int n,m,s,t;
void in(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i][1],&a[i][2]);
    }
    memset(f,127,sizeof(f));
    scanf("%d",&m);
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        f[x][y]=f[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
    }
    scanf("%d%d",&s,&t);
}
void dij(){
    memset(b,0,sizeof(b));
    b[s]=1;
    c[s]=0;
    for(int i=1;i<=n;i++){
        c[i]=f[s][i];
    }
    double minl;
    for(int i=1;i<n;i++){
        minl=1e30;
        int k=0;
        for(int j=1;j<=n;j++){
            if((!b[j])&&(c[j]<minl)){
                minl=c[j];
                k=j;
            }
        }
		if(k==0){
	            break;
        }
        b[k]=1; 
        for(int j=1;j<=n;j++){
            if(c[k]+f[k][j]<c[j]){
                c[j]=c[k]+f[k][j];
            }
        }
   }
}
void out(){
    printf("%.2lf",c[t]);
}
int main(){
    in();
    dij();
    out();
    return 0;
}
2.priority_queue优化
优先队列优化 




3.spfa算法

优点：可解负边权问题，时间复杂度为O(kn),k常数较小，因此快，可优化

缺点：可被特殊构造的数据卡掉退化为O(mn)

啊这，spfa优化很多但都容易被hack掉退化成原形，所以考场少用SPFA

为已死的SPFA默哀

由于蒟蒻啥样的SPFA优化不会并且无优化SPFA都几乎没打过，所以直接贴代码跑路了



点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define map mymap
queue<int>q;
int n,m,map[2021][2022],dis[2005];
bool vis[2005];
void spfa(){
	q.push(1);
	vis[1]=true;
	dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=1;i<=n;i++){
			if(map[x][i]>0&&(min(dis[x],map[x][i])>dis[i]||!dis[x])){
				if(!dis[x]){
					dis[i]=map[x][i];
				}
				else{
					dis[i]=min(dis[x],map[x][i]);
				}
				if(!vis[i]){
					vis[i]=true;
					q.push(i);
				}
			}
		}
	}
} 
int main(){
	scanf("%d",&n);
	memset(map,0,sizeof(map));
	for(int i=2;i<=n;i++){
		dis[i]=0;
	}
	int f,t,p;
	while(scanf("%d%d%d",&f,&t,&p)==3){
		if(!f&&!t&&!p){
			break;
		}
		else{
			map[f][t]=p;
		}
	}
	spfa();
	for(int i=2;i<=n;i++){
		printf("%d\n",dis[i]);
	}
	return 0;
}





综上：把堆优化Dijsktra和SPFA打熟是绝对有好处的据说网络流有用，不过蒟蒻fw一个管他网啥

                    

                        这篇关于最短路算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
                    


                


                
                
 

                
                

                    

                        
您可能喜欢

                        
                    

                

                

            

             
            
            
            
        

        
        

        

            

                
栏目导航