poj3259

传送门

第一种方法:Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, w;
#define MAX 10005
struct node{
int u, v, t;
}p[5210];

void Bellman_Ford(){
int dis[505];
memset(dis, MAX, sizeof(dis));
dis[1] = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j <= 2 * m + w; j++)
dis[p[j].v] = min(dis[p[j].v], dis[p[j].u] + p[j].t);
int flag = 0;
for(int i = 1; i <= 2 * m + w; i++)
if(dis[p[i].v] > dis[p[i].u] + p[i].t){
flag = 1;
break;
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}

int main(){
int f;
cin >> f;
while(f--){
cin >> n >> m >> w;
for(int i = 1; i <= 2 * m - 1; i += 2){
cin >> p[i].u >> p[i].v >> p[i].t;
p[i + 1].v = p[i].u;
p[i + 1].u = p[i].v;
p[i + 1].t = p[i].t;
}
for(int i = 2 * m + 1; i <= 2 * m + w; i++){
cin >> p[i].u >> p[i].v >> p[i].t;
p[i].t = -p[i].t;
}
Bellman_Ford();
}
return 0;
}

/*
Input:
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
Output:
NO
YES
*/

Bellman-Ford算法及SPFA算法

Bellman-Ford算法

Bellman-Ford算法能解决存在负权边的单源点最短路径问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Bellman_Ford(){
bool f;
for(int i = 0; i < n; i++){
f = false;
for(int j = 0; j < m; j++){
int x = edge[j].from;
int y = edge[j].to;
int z = edge[j].v;
if(dis[x] + z < dis[y]){
dis[y] = dis[x] + z;
f = true;
}
}
if(!f) break;
if(i == n - 1 && f) return false; //表示图中存在负权环(因为从源点出发到n-1个结点,而n-1遍还没有更新完毕)
}
return true; //表示找到了最短路
}

几点解释:

m是什么? 图中一共有m条边。

为什么松弛的过程要循环n次? 因为在进行了一次寻找可松弛边的循环(我们暂且将它称为m循环)后,结果只有两种情况。

第一种情况:没找到可松弛边,此时 f 仍旧等于 false,n循环直接break了;

第二种情况:找到了可松弛边。无论在第一轮m循环中松弛了多少次,总会有一次松弛得到的是源点到目标点的最短距离,否则就出现负权环了。此时按照这种最坏假设,循环 n-1 次就一定可以使 n-1 个点都找到各自到源点的最短路径。

SPFA算法

SPFA (shortest path faster algorithm) 是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。(SPFA是Bellman-Ford的优化)

Bellman-Ford算法的复杂度较高,中间进行了一些不必要的计算,因为并不是每个顶点都会在松弛操作中改变。SPFA算法在最坏情况下的复杂度很高,但是在正常情况下点的平均入队次数不大于2。

Bellman-Ford能实现的,都可以用SPFA来解决,所以一般都会用SPFA。

基本思想是:使用队列,初始时队列里只有源点,dis 记录源点到所有点的最短路径 (初始时为无穷,若源点为s,则 dis[s] = 0。除了起点赋值为0外,其他顶点的对应的dis的值都赋予无穷大,这样有利于后续的松弛),然后用队列里的点更新 dis 数组的值,如果某点的 dis 值被更新,则将该点加入到队尾。重复执行直到队列为空。

如果存在一点进入队列的次数大于等于 n 次,则存在负权环。(当图中有负权环时,队列就不会有空的情况了,因为由于负权环的存在,负权环上的点就可以一直被松弛,一直能被松弛就代表着队列会不断反复让负权环上的点入队出队,程序就会死循环)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool spfa(){  //SPFA判断负权环
for(int i = 0; i != top; i++){
int x = q[i]; //取队列元素,数组q模拟队列
have[x] = 0; //出队,have[x] = 0 表示x已经不在队列中
for(int j = 0; j < head[x].size(); j++){
y = head[x][j].to;
z = head[x][j].v;
if(dis[x] + z < dis[y]){
dis[y] = dis[x] + z;
if(!have[y]){ //如果y不在队列中
have[y] = 1; //将y入队
q[top++] = y; //加到队尾
cnt[y]++; //记录结点y入队次数
if(cnt[y] >= n) //存在负权环
return true;
}
}
}
}
return false; //不存在负权环
}

关于SPFA的一篇很详细的博客:

https://blog.csdn.net/qq_35644234/article/details/61614581