您的位置: 首页  >  文章  >  【算法】【ACM】POJ 3259 Wormholes（Bellman-Ford算法， SPFA ，FLoyd算法）

【算法】【ACM】POJ 3259 Wormholes（Bellman-Ford算法， SPFA ，FLoyd算法）

分类: 文章 • 2024-11-30 16:30:28

Bellman-Ford算法

Bellman-Ford算法的优点是可以发现负圈，缺点是时间复杂度比Dijkstra算法高。而SPFA算法是使用队列优化的Bellman-Ford版本，其在时间复杂度和编程难度上都比其他算法有优势。

Bellman-Ford算法流程分为三个阶段：

  • 第一步：数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；

  • 第二步：以下操作循环执行至多n-1次，n为顶点数： 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

  • 第三步：为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

v的最短距离保存在 d[v]中。

在这个算法中，需要了解的几点

1、只有上一次迭代中松驰过的点才有可能参与下一次迭代的松弛操作。

似乎算法在遍历每一条边的做法会浪费时间，或许我们只需要考虑那些被成功松弛的点的邻点就可以了。我们可以用一个队列来维护这些被成功松弛的点，这个小小的改进可以节省很多时间，改进后的算法叫做SPFA。

2、迭代的实际意义：每一次迭代k中，我们找到了经历了k条边的最短路

3、没有点能够松弛时，迭代结束

Bellman-Ford(G,w,s) ：boolean   //图G ，边集 函数 w ，s为源点
 
1        for each vertex v ∈ V（G） do        //初始化 1阶段
 
2            d[v] ←+∞
 
3        d[s] ←0;                             //1阶段结束
 
4        for i=1 to |v|-1 do               //2阶段开始，双重循环。
 
5           for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。
 
6              If d[v]> d[u]+ w(u,v) then      //松弛判断
 
7                 d[v]=d[u]+w(u,v)               //松弛操作   2阶段结束
 
8        for each edge（u,v） ∈E(G) do
 
9            If d[v]> d[u]+ w(u,v) then
 
10            Exit false
 
11    Exit true

SPFA

算法特点：在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。 

关键词：初始化 relax 队列

实现的过程和Bellman_Ford类似

【初始化】

dis数组全部赋值为INF，pre数组全部赋值为-1（表示还不知道前驱），

dis[s] = 0 表示源点不要求最短路径（或者最短路径就是0）。

【队列+松弛操作】

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队，这样不断从队列中取出顶点来进行松弛操作。

以此循环，直到队空为止就完成了单源最短路的求解。

【算法过程】

设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点 u，并且用 u 点当前的最短路径估计值dis[u]对与 u 点邻接的顶点 v 进行松弛操作，如果 v 点的最短路径估计值dis[v]可以更小，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。

【检测负权回路】

方法：如果某个点进入队列的次数大于等于 n，则存在负权回路，其中 n 为图的顶点数。

#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <cstdio>
#include <functional>
using namespace std;

const int maxn = 99999999;
int map[205][205];//邻接矩阵
int d[205];//源点到顶点i的最短距离
bool vis[205];//标记数组
int enqueue_num[205];//记录入队次数
int path[205];//记录最短的路径
int n;//顶点数
int e;//边数
int start;//源点

bool SPFA()
{
	memset(vis,false,sizeof(vis));
	memset(enqueue_num,0,sizeof(enqueue_num));
	for(int i=0;i<n;i++)
	{
		d[i] = maxn;
		path[i] = start;
	}
	queue<int> Q;
	Q.push(start);
	d[start] = 0;
	vis[start] = 1;
	enqueue_num[start]++;
	int v;
	while(Q.empty()!=1)
	{
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
		for(v=0;v<n;v++)
		{
			if(map[u][v]!=maxn)//u 与 v 直接邻接
			{
				if(d[u]+map[u][v]<d[v])
				{
					d[v] = d[u] + map[u][v];
					path[v] = u;
					if(!vis[v])
					{
						Q.push(v);
						enqueue_num[v]++;
						if(enqueue_num[v]>=n)
						{
							return false;
						}
						vis[v] = true;
					}
				}
			}
		}
	}
	return true;
}

void print()
{
	int i;
	for(i=0;i<n;i++)
	{
		if(i!=start)
		{
			int p = i;
			stack<int> s;
			cout << "顶点 " << start << " 到顶点 " << p << "最短路是：";
			while(start!=p)
			{
				s.push(p);
				p=path[p];
			}
			cout << start;
			while(s.empty()!=1)
			{
				cout << "---" << s.top();
				s.pop();
			}
			cout << "    最短路径的长度是：" << d[i] << endl; 
		}
	}
}

int main()
{
	int i, j;
	cout << "请输入图的顶点数，边数，源点：\n";
	cin >> n >> e >> start;
	//初始化
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			if(i==j)	map[i][j] = 0;
			else	map[i][j] = maxn;
		}
	}
	cout << "请输入" << e << "条边的信息：\n";
	int u, v, w;
	//默认是有向图
	for(i=0;i<e;i++)
	{
		cin >> u >> v >> w;
		map[u][v] = w;
	}
	if(SPFA())
		print();
	else
		cout << "Sorry,it has negative circle!\n";
	return 0;
}

用下面这张图进行测试数据： 

【算法】【ACM】POJ 3259 Wormholes（Bellman-Ford算法， SPFA ，FLoyd算法） 

【算法】【ACM】POJ 3259 Wormholes（Bellman-Ford算法， SPFA ，FLoyd算法） 

 

现学现用

http://poj.org/problem?id=3259

【问题描述】

虫洞是很奇特的，因为它是一个**单向**通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的图（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都回到不大于10000秒之前。

【Input】

第1行：一个整数F表示接下来会有F个农场说明。 每个农场第一行：分别是三个空格隔开的整数：N，M和W 第2行到M+1行：三个空格分开的数字（S，E，T）描述，分别为：需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述虫洞，描述单向路径，S到E且回溯T秒。

【Output】

F行，每行代表一个农场 每个农场单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求

【样例输入】

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

【样例输出】

NO
YES

题意是问是否能通过虫洞回到过去；虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退T秒。我们把虫洞看成是一条负权路，问题就转化成求一个图中是否存在负权回路；

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 9999999;

typedef struct Edge
{
	int u,v;
	int weight;
}Edge;
Edge edge[5200]; 
int d[1010];
int N,M,W,F,all_e;

bool bellman_ford()
{
	int i,j;
	bool flag;
	for(i=1;i<=N-1;i++)
	{
		flag = false;
		for(j=0;j<all_e;j++)
		{
			if(d[edge[j].v]>d[edge[j].u]+edge[j].weight)
			{
				d[edge[j].v]=d[edge[j].u]+edge[j].weight;
				flag = true;
			}
		}
		if(!flag)	
			return false;//不存在负环
	}
	for(i=0;i<all_e;i++)
	{
		if(d[edge[i].v]>d[edge[i].u]+edge[i].weight)
			return true;//存在
	}
	return false;
}

int main()
{
	int i,j;
	cin >> F;
	while(F--)
	{
		cin >> N >> M >> W;
		memset(d,maxn,sizeof(d));
		all_e = 0;
		int u,v,w;
		//注意是无向图,双向的
		for(i=1;i<=M;i++)
		{
			cin >> u >> v >> w;
			edge[all_e].u = u;
			edge[all_e].v = v;
			edge[all_e++].weight = w;
			edge[all_e].u = v;
			edge[all_e].v = u;
			edge[all_e++].weight = w;
		}
		//题目中明确指出，虫洞是单向的
		for(i=1;i<=W;i++)
		{
			cin >> u >> v >> w;
			edge[all_e].u = u;
			edge[all_e].v = v;
			edge[all_e++].weight = -w;
		}
		if(bellman_ford())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}

Floyd算法也可以求解，但是，很容易就超时，AC的话时间也会比Bellman_ford算法多很多

【算法】【ACM】POJ 3259 Wormholes（Bellman-Ford算法， SPFA ，FLoyd算法）

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 99999999;
int map[520][520];
int F,N,M,W;

bool bellman_ford()
{
	int i,j,k;
	for(k=1;k<=N;k++)
	{
		for(i=1;i<=N;i++)
		{
			for(j=1;j<=N;j++)
			{
				if(map[i][j]>map[i][k]+map[k][j])
				{
					map[i][j]=map[i][k]+map[k][j];
				}
			}
			if(map[i][i]<0)
			{
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i,j;
	cin >> F;
	while(F--)
	{
		cin >> N >> M >> W;
		for(i=0;i<=N;i++)
		{
			for(j=0;j<=N;j++)
			{
				if(i==j)	map[i][j] = 0;
				else	map[i][j] = maxn;
			}
		}
		int a,b,w;
		//需要注意的是：正权的边是单向的，负权的边是双向的。
		for(i=1;i<=M;i++)
		{
			cin >> a >> b >> w;
			if(map[a][b]>w)
			{
				map[a][b] = w;
				map[b][a] = w;
			}
		}
		for(i=1;i<=W;i++)
		{
			cin >> a >> b >> w;
			map[a][b] = -w;
		}
		if(bellman_ford())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}

推荐博客：

最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)

 

相关推荐