朴素法
可以用来找负环
但复杂度较高 一般不用它 时间复杂度$O(nm)$ 用SPFA
枚举$n$轮 然后枚举每个点的每条边共 $m$ ， 所以$O(nm)$
为什么能找负环
若有$n$个点则有$n-1$条边. 那么最短路也就最多只有$n-1$条
既 松弛也只会进行$n-1$轮 若进行到$n$轮 还能存在松弛操作 由抽屉原理 必然存在两个相同的点， 说明存在环
算法流程
枚举$n$轮循环
枚举每个点的每条边 进行松弛操作
如何检测负环
在每轮循环初始化flag为false , 若去枚举每条边的过程中发现没更新 既 flag还是false 直接break退出循环即可 因为往后的每一轮都不会更新了，若更新了则直接标记为true
若$n$轮循环都走完了 ，返回的flag还是为true,则说明有环
与优化过的dijkstra相比
dj是找到一个最小的点然后去不断更新下面新的一层
可正确处理负边权环 , dj 可不可以加上某一个数值 转化为正值来求最短路？不行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int d[N];
int n , m;
bool bellman(int x){
memset(d,0x3f,4*(n+1));d[x] = 0;
bool flag;
for(int i = 1;i<=n;++i){
flag = false;
for(int u =1;u<=n;++u){
if(d[u] == inf) continue;//都无限大距离肯定不是最小 小优化 直接跳过即可
for(int j = h[u];~j;j = e[j].next){
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
flag = true;
}
}
}
if(!flag) break;
}
return flag;//true 有环
}
|
spfa ver.1队列优化
显然不是每个点都需要枚举边，只要枚举更新过的点就行了，没更新过的上一次就是距离不是最小的 . 那么需要维护一个队列 把更新过的点的出度放入(只有没有在队列的的才放入 防止环) 用一个bool数组维护。
再用一个距离数组来维护距离 若 距离 >= n 则 说明存在环 返回即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
bool spfa(int x){
queue<int> q; vis[x] = true; q.push(x);d[x] = 0;
while(q.size()){
int u = q.front();q.pop();vis[u] = false;
for(int j = h[u];~j;j = e[j].next){
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
cnt[v] = cnt[u] + 1;//从0开始
if(cnt[v] >= n) return true;//存在环
if(!vis[v]) q.push(v) , vis[v] = true;
}
}
}
return false;
}
|
spfa ver.2
…待补充 与防卡SPFA斗争中..