最短路径算法——两种算法解

2024-12-29 10:57:32

发布于：广东

19阅读

0回复

0点赞

bellman_ford算法

#include<bits/stdc++.h>
using namespace std;
struct node{
	int from,to,len;
}a[15555];
int dis[10005];
int n,m,w,x,y,z,s,t;
void bellman_ford(){
	int from,to,len;
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			from=a[j].from;
			to=a[j].to;
			len=a[j].len;
			if(dis[to]>dis[from]+len){
				dis[to]=dis[from]+len; 
			}	 
		}
	}
	printf("%d",dis[t]);
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=n;i++){
		dis[i]=1e9;
	}
	dis[s]=0;
	for(int i=1;i<=m;i++){
		cin>>a[i].from>>a[i].to>>a[i].len;
	}
	bellman_ford();
	return 0;
}

spfa算法（算法复杂度比bellman_ford算法低）

#include<bits/stdc++.h>
using namespace std;
int n,m,w,x,y,z,s,t;
int dis[2505],vis[2505];
int a[5555][5555]; 
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=n;i++) dis[i]=1e9;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=1e9; 
		} 
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		a[x][y]=z;
	}
	dis[s]=0;
	vis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=1;i<=n;i++){
			if(dis[i]>dis[u]+a[u][i]){
				dis[i]=dis[u]+a[u][i];
				if(!vis[i]){
					vis[i]=1;
					q.push(i);
				} 
			}
		}
	}
	cout<<dis[t];
	return 0;
}
/*
spfa 
1.初始化dis[]数组，dis[v]=无穷大
2.定义队列，起点入队
3.当队列不为空
	1)获取队头head，队头出队，标记队头不在队列中
	2)看队列能到哪些相邻的终点v；len是head---->v的当前距离
	注意 一旦v更新的时候，如果v不在队列中，那还需要入队并标记在队列中
4.队列为空，则算法结束，输出dis数组，则可以知道单源最短路径 
*/