勇敢小鸡，不怕困难。时隔多日，又来复习图论算法了，本来想的是搞一下差分约束的，但是发现前置知识是spfa算法，所以就先来学习一下这个。

spfa算法介绍

SPFA算法是求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。

算法的思路： 我们用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

我们要知道带有负环的图是没有最短路径的，所以我们在执行算法的时候，要判断图是否带有负环，方法有两种：

  1. 开始算法前，调用拓扑排序进行判断（一般不采用，浪费时间）
  2. 如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）

spfa算法浅谈

spfa算法的话，一般单源最短路基本用不到 ，dijkstra算法比它优很多，唯有需要处理负权图的时候会想到他。差分约束无解的情况就是存在负环，因此这个得学。

大概流程可以描述为以下文字。

  1. 源点入队，源点距离初始化为0，其它初始化为 \(inf\)。
  2. 出队一个点并遍历与之之间相连的点，进行松弛操作。也就是我们经常见到的 if(dis[to]>w+dis[from])dis[to]=dis[from+w]。
  3. 如果对一个点进行了松弛那么判断它有没有在队列中，如果不在则入队，并判断入队次数有没有超过点的个数，如果超过则goto 6。
  4. 如果队列不为空则goto 2。
  5. 结束，输出结果。
  6. 结束，输出存在负环的对应答案。

下面来一道例题。

洛谷P1396

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s区。

该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。

题目分析

这题其实有点差强人意，因为这个是要判断所经过边的最大值的最小值，但是我们主要还是练习spfa为主。

标程

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
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
struct eee{
    int to;
    int next;
    int w;
}edge[maxn<<2];
int root[maxn],cnt,dis[maxn],in_que[maxn];
int n,m,s,t;
void add(int x,int y,int w){
    edge[++cnt].to=y;
    edge[cnt].w=w;
    edge[cnt].next=root[x];
    root[x]=cnt;
}
void sync(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    queue<int>q;
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=root[u];i;i=edge[i].next){
            int v=edge[i].to,w=edge[i].w;
            //printf("%d %d %d\n",u,v,w);
            if(dis[v]>max(dis[u],w)){
                dis[v]=max(dis[u],w);
                if(!in_que[v]){
                    q.push(v);
                    in_que[v]=1;
                }
                
            }
        }
        in_que[u]=0;
    }
}
int main(){
    //freopen("P1396_1.in","r",stdin);
    sync();
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    spfa();
    printf("%d\n",dis[t]);
    return 0;
}