欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法概论》实验—图:带负权值边的有向图中的最短路径路径问题

程序员文章站 2024-03-17 14:22:10
...

题目描述
对于一个带负权值边的有向图,实现Bellman-Ford算法,求出从指定顶点s到其余顶点的最短路径,并判断图中是否存在负环。
Bellman-Ford算法的基本思路
对图中的边进行V-1轮操作(为什么是V-1轮?除了起始点,就只有V-1个点了,一个点的最短路径经过的点的数目不会再超过V-1了,所以最多只用进行V-1轮更新),每轮都遍历图中所有的边:对每条边u->v,如果以u为中介点可以使d[v]更小,即d[u]+l[u->v]<d[v]成立时,就用d[u]+l[u->v]更新d[v](松弛操作)。V-1轮操作,每轮都遍历图中所有的边,所以Bellman-Ford算法的时间复杂度是O(VE)。
存在问题及改进(SPFA算法)
问题:只有当某个顶点u的d[u]值改变时,从它出发的边的邻接顶点d[v]值才可能改变(想想为什么?如果d[v]需要以u作为中介点,那d[v]一定会变,如果不需要,那么改变后的d[u])可能让u作为中介点变为一个更佳的选择。所以不需要每一轮都遍历所有边
改进:根据上一段加粗部分说的问题,可以建立一个队列,把每次改变了d[ ]值的点加进去。每次将队首顶点u取出,然后遍历每条边u->v,进行松弛操作,对于获得了更优值的d[v],如果d[v]不在队列中,就加进去,已经在里面就不用说了。这样就有结束条件:队列为空(说明图中没有从源点可到达的负环),或者从某个顶点的入队次数超过V-1(最多用V-1次就可以把所有的点优化一次,再多就说明有个从源点可到达的负环啦,那就转一圈最短路径就变小一次,肯定是不行滴)。
这种优化后的算法也叫做SPFA算法
代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXV = 20;//最大顶点数
const int INF = 100000;//无穷大
struct Node
{
	int v, dis;//v为邻接边的目标顶点,dis是边权
};
vector<Node> Adj[MAXV];//邻接表
int V;//顶点数
int E;//边数
int d[MAXV];//起点到达各点的最短路径长度
int num[MAXV];//记录顶点的入队次数
bool inq[MAXV];//记录顶点是否在队列里
bool Bellman(int s)//指定顶点s
{
	for (int u = 0; u < V; u++)
	{
		d[u] = INF;
		num[u] = 0;
		inq[u] = false;
	}
	queue<int> Q;
	Q.push(s);//源点入队
	inq[s] = true;//源点已入队
	num[s]++;//源点入队次数加一
	d[s] = 0;//源点的d显然为0
	while (!Q.empty())
	{
		int u = Q.front();//队首顶点编号为u
		Q.pop();//出队
		inq[u] = false;//设置u不在队列中
		//遍历u的所有邻接边v
		for (int j = 0; j < Adj[u].size(); j++)
		{
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;
			if (d[v] > d[u] + dis)
			{
				d[v] = d[u] + dis;//松弛操作
				if (!inq[v])//如果v不在队列里
				{
					Q.push(v);
					inq[v] = true;
					num[v]++;
					if (num[v] >= V)//说明又可到达负环
						return false;
				}
			}
		}
	}
	return true;
}
int main()
{
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		int u, v,dis;
		cin >> u >> v>>dis;
		Node e;
		e.v = v;
		e.dis = dis;
		Adj[u].push_back(e);//注意一个问题vector是从0开始的
	}
	int s;
	cin >> s;//指定顶点
	bool judge = Bellman(s);
	for (int i = 0; i < V; i++)
	{
		cout << "到达点"<<i<<"的最短路径是:"<<d[i]<<endl;//出从指定顶点s到其余顶点的最短路径,其中s到s的为0
	}
	if (!judge)
		cout << "图中存在负环" << endl;
	return 0;
}

测试样例与结果
《算法概论》实验—图:带负权值边的有向图中的最短路径路径问题

6 9
0 1 10
1 2 -4
0 4 4
1 4 1
0 5 2
5 4 1
4 3 6
3 1 -5
3 2 2
0
到达点0的最短路径是:0
到达点1的最短路径是:4
到达点2的最短路径是:0
到达点3的最短路径是:9
到达点4的最短路径是:3
到达点5的最短路径是:2

参考资料《算法笔记》胡凡
里面有一点点是我自己的想法吧QAQ,希望自己可以通过写博客慢慢进步,最后能写出更具独创性的博客。

相关标签: 算法概论