求最短路之Bellman-Ford算法

2018年3月9日 2点热度 0条评论 来源: 爱上键盘的小哥哥

算法思路:

Bellman-Ford算法是通过边进行松弛,即枚举每一条边,然后比较源点到边的终点的估计最短路径估计值和源点到该边的起点的估计最短路径估计值加上边长

复杂度:O(nm) n为点数,m为边数

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1005;
struct node{
	int u;
	int v;
	int val;
	int next;
}edge[N*N];
int head[N],cnt;
int dis[N];
int n,m;
void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
}
void add(int from,int to,int val){
	edge[cnt].u=from;
	edge[cnt].v=to;
	edge[cnt].val=val;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
void BellmanFord(int s){
	memset(dis,Inf,sizeof(dis));
	dis[s]=0;
	for(int k=0;k<n;k++){
		for(int i=0;i<cnt;i++){
			int u=edge[i].u,v=edge[i].v;
			if(dis[v]>dis[u]+edge[i].val){
				dis[v]=dis[u]+edge[i].val;
			}
		}
	}
	int flag=0;
	for(int i=0;i<cnt;i++){
		int u=edge[i].u,v=edge[i].v;
		if(dis[v]>dis[u]+edge[i].val){
			flag=1;
			break;
		}
	}
	if(flag) printf("有负权回路!\n");
	for(int i=1;i<=n;i++)
	  printf("%d ",dis[i]);
	  
}
int main(){
	scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	BellmanFord(1);
	return 0;
}

优化版本SPFA(n*m)

vis[ i ]表示点i在队列里

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1005;
struct node{
	int to;
	int val;
	int next;
}edge[N*N];
int head[N],cnt;
int dis[N],vis[N];
int n,m;
void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
}
void add(int from,int to,int val){
	edge[cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
void SPFA(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,Inf,sizeof(dis));
	queue<int>p;
	p.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!p.empty()){
		int u=p.front();
		p.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].val){
				dis[v]=dis[u]+edge[i].val;
				if(!vis[v]){
					vis[v]=1;
					p.push(v);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	   printf("%d ",dis[i]);
}
int main(){
	scanf("%d%d",&n,&m);
	init();
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	SPFA(1);
	return 0;
}

    原文作者:爱上键盘的小哥哥
    原文地址: https://blog.csdn.net/islittlehappy/article/details/79498911
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。