信息学奥赛一本通 1508：Easy SSSP

【题目链接】

ybt 1508：Easy SSSP

【题目考点】

1. SPFA算法

• SPFA可以求存在负权边的图的单源最短路径
• SPFA算法判断图中是否存在负环
• SPFA_DFS算法判断图中是否存在负环

【解题思路】

使用SPFA统计整个图中是否有负环，初始需要将所有顶点都入队。
可以假想存在一个超级源点，第0号顶点。第0号顶点到第1到第n号顶点都有权值为0的边。
以顶点0为源点执行SPFA算法，统计顶点的入队次数，如果某顶点入队次数大于n，则存在负权环。

判断是否存在负权环可以使用Bellman-Ford算法栈优化，即使用DFS实现SPFA，效率更高。运行前，将dis数组初值设为0，尝试从每个顶点出发执行SPFA_DFS，访问到顶点u时，将该顶点u入栈。结束访问顶点u时，将该顶点u出栈。如果在访问顶点u的邻接点v时，发现顶点v已经在栈内，那么存在一个负权环。

而后再以S为源点调用SPFA算法求单源最短路径。

【题解代码】

解法1：SPFA算法找负环和求最短路径 设超级源点

#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f3f3f3f3f
struct Edge
{
	int v, w;
};
long long n, m, s, dis[N], enqueNum[N];
vector<Edge> edge[N];
bool inQue[N];
bool spfa(int sv)//返回是否有负环 
{
	memset(dis, 0x3f, sizeof(dis));
	queue<int> que;
	dis[sv] = 0;
	que.push(sv);
	inQue[sv] = true;
	enqueNum[sv]++;
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inQue[u] = false;
		for(Edge e : edge[u])
		{
			int v = e.v, w = e.w;
			if(dis[v] > dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!inQue[v])
				{
					if(++enqueNum[v] > n)
						return true;		
					que.push(v);
					inQue[v] = true;
				}
			}
		}
	}
	return false;
}
int main()
{
	int u, v, w;
	cin >> n >> m >> s;
	for(int i = 1; i <= m; ++i)
	{
		cin >> u >> v >> w;
		edge[u].push_back(Edge{v, w});
	}
	for(int i = 1; i <= n; ++i)//添加超级源点
		edge[0].push_back(Edge{i, 0}); 
	bool hasNegRing = spfa(0);
	if(hasNegRing)
		cout << -1;
	else
	{
		spfa(s);
		for(int i = 1; i <= n; ++i)
		{
			if(dis[i] == INF)
				cout << "NoPath" << '\n';
			else
				cout << dis[i] << '\n';
		}
	}
	return 0;
}

解法2：尝试从每个顶点出发调用SPFA_DFS算法找负环，SPFA求最短路径

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f3f3f3f3f
struct Edge
{
	int v, w;
};
int n, m, s;
long long dis[N];
vector<Edge> edge[N];
bool inStk[N], inQue[N], hasNegRing;
void spfa_dfs(int u)
{
	if(hasNegRing)
		return;
	inStk[u] = true;
	for(Edge e : edge[u])
	{
		int v = e.v, w = e.w;
		if(dis[v] > dis[u]+w)
		{
			dis[v] = dis[u]+w;
			if(inStk[v])//找到负环 
			{
				hasNegRing = true;
				return;
			}
			spfa_dfs(v);
		}
	}
	inStk[u] = false;
}
void spfa_bfs(int u)
{
	memset(dis, 0x3f, sizeof(dis));
	queue<int> que;
	inQue[u] = true;
	dis[u] = 0;
	que.push(u);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inQue[u] = false;
		for(Edge e : edge[u])
		{
			int v = e.v, w = e.w;
			if(dis[v] > dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!inQue[v]) 
				{
					inQue[v] = true;
					que.push(v);
				}
			}
		}	
	}
}
int main()
{
	int f, t, w;
	cin >> n >> m >> s;
	for(int i = 1; i <= m; ++i)
	{
		cin >> f >> t >> w;
		edge[f].push_back(Edge{t, w});
	}
	for(int v = 1; v <= n; ++v)
	{
		spfa_dfs(v);
		if(hasNegRing)
		{
			cout << -1;
			return 0;
		}
	}
	spfa_bfs(s);
	for(int i = 1; i <= n; ++i)
	{
		if(dis[i] == INF)
			cout << "NoPath" << endl;
		else
			cout << dis[i] << endl;
	}
	return 0;
}