最短路径算法——两种算法解
2024-12-29 10:57:32
发布于：广东
10阅读
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数组，则可以知道单源最短路径
*/
有帮助，赞一个