【题目链接】
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';elsecout << 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;elsecout << dis[i] << endl;}return 0;
}
