SPFA算法（判断负权回路，求最短路径）（851，852）

851. spfa求最短路

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1

号点到 n 号点的最短距离，如果无法从 1 号点走到 n

号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n

和 m

。

接下来 m

行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z

。

输出格式

输出一个整数，表示 1

号点到 n

号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105

,
图中涉及边长绝对值均不超过 10000

。

输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

 解法一：SPFA算法

 * Bellman_Ford 算法是每一轮松弛迭代都会对所有边进行比较，看是否能够进行松弛操作，这就
 * 造成了很多没必要的比较，想想，只有当该边被松弛了，那么后面与该边相连接的边才能够被
 * 松弛， 因此我们可以只记录被松弛的边，没被松弛的边就不用管它。
 * 这就是著名的SPFA算法，我们用一个队列来存储被松弛的边。

/**
 * Bellman_Ford 算法是每一轮松弛迭代都会对所有边进行比较，看是否能够进行松弛操作，这就
 * 造成了很多没必要的比较，想想，只有当该边被松弛了，那么后面与该边相连接的边才能够被
 * 松弛， 因此我们可以只记录被松弛的边，没被松弛的边就不用管它。
 * 这就是著名的SPFA算法，我们用一个队列来存储被松弛的边。
 */
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
 
const int maxn = 1e5+10 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
void SPFA(int st)
{
    queue<int> q;
    q.push(st);
    fill(d,d+maxn,INF);
    d[st]=0;
    hs[st]=1;
    
    while(q.size())
    {
        int u=q.front();
        q.pop();
        hs[u]=0;
        for(int i=0;i<Adj[u].size();++i)
        {
            int v=Adj[u][i].v,w=Adj[u][i].w;
            if(d[u]+w < d[v])
            {
                d[v]=d[u]+w;
                if(hs[v]==0)
                    q.push(v);
            }
        }
        
    }
}
 
int main()
{
    Read();
    
    SPFA(1);
    
    if(d[Nv] > INF/2)
        puts("impossible");
    else 
        cout << d[Nv] << endl;
 
    return 0;
    
}

解法二：Bellman_Ford算法

/**
 * Bellman_Ford 算法：经过Nv-1 条边松弛，从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 *
 * 对于Bellnan_Ford 算法最坏时间复杂度是 O(NM),但是往往还未达到Nv-1轮松弛前就已经计算出
 * 最短路径了，所以我们可以用一个 flag变量来标记此轮松弛操作是否该改变了dis数组的值，如果
 * 没有改变，就提前退出，可以减少相当多的时间消耗；
 *
 * 我说怎么能AC，原来是保证不会存在负权回路，当有负权回路的时候，该算法一定是最坏时间复
 * 杂度；
*/

/**
 * Bellman_Ford 算法：经过Nv-1 条边松弛，从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 * 
 * 对于Bellnan_Ford 算法最坏时间复杂度是 O(NM),但是往往还未达到Nv-1轮松弛前就已经计算出
 * 最短路径了，所以我们可以用一个 flag变量来标记此轮松弛操作是否该改变了dis数组的值，如果
 * 没有改变，就提前退出，可以减少相当多的时间消耗；
 * 
 * 我说怎么能AC，原来是保证不会存在负权回路，当有负权回路的时候，该算法一定是最坏时间复
 * 杂度；
*/
 
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
typedef pair<int,int> PII;
 
const int maxn = 1e5+10 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
void Bellman_Ford(int st) //各点到st顶点的最短距离
{
    fill(d,d+maxn,INF);
    d[st]=0;
 
    for(int k=1;k<Nv;++k)
    {
        int flag=0;
        for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])
                {
                    d[v]=d[u]+w;
                    flag=1;
                }
            }
        if(flag == 0)
            break;
    }
}
 
int main()
{
    Read();
 
    Bellman_Ford(1);
 
    if(d[Nv] > INF/2)
        puts("impossible");
    else 
        cout << d[Nv] << endl;
 
    return 0;
 
}

852. spfa判断负环

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n

和 m

。

接下来 m

行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z

。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

1≤n≤2000

,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000

。

输入样例：

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

Yes

 解法一：SPFA算法

/**
 * Bellman_Ford 算法是每一轮松弛迭代都会对所有边进行比较，看是否能够进行松弛操作，这就
 * 造成了很多没必要的比较，想想，只有当该边被松弛了，那么后面与该边相连接的边才能够被
 * 松弛， 因此我们可以只记录被松弛的边，没被松弛的边就不用管它。
 * 这就是著名的SPFA算法，我们用一个队列来存储被松弛的边。
 *
 * 如果每一个顶点被Nv条边进行了松弛操作（一个无自环的顶点，最多只有Nv-1条边与其相连），
 * 那么一定出现了负环；用一个 num 数组来记录每个顶点被松弛的边的数目
*/

/**
 * Bellman_Ford 算法是每一轮松弛迭代都会对所有边进行比较，看是否能够进行松弛操作，这就
 * 造成了很多没必要的比较，想想，只有当该边被松弛了，那么后面与该边相连接的边才能够被
 * 松弛， 因此我们可以只记录被松弛的边，没被松弛的边就不用管它。
 * 这就是著名的SPFA算法，我们用一个队列来存储被松弛的边。
 * 
 * 如果每一个顶点被Nv条边进行了松弛操作（一个无自环的顶点，最多只有Nv-1条边与其相连），
 * 那么一定出现了负环；用一个 num 数组来记录每个顶点被松弛的边的数目
*/
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
 
const int maxn = 1e5+10 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
int num[maxn]; //记录每个顶点有多少条边能够使其松弛
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
bool SPFA(int st) //出现负环，返回true
{
    queue<int> q;
    fill(d,d+maxn,INF);
    d[st]=0;
    for(int i=1;i<=Nv;++i)
    {
        q.push(i);  //要将所有顶点都入队，只入队某一个顶点，可能从该顶点出发并不能
        hs[i]=1;    //到达负环
    }
    
    while(q.size())
    {
        int u=q.front();
        q.pop();
        hs[u]=0;
        for(int i=0;i<Adj[u].size();++i)
        {
            int v=Adj[u][i].v,w=Adj[u][i].w;
            if(d[u]+w < d[v])
            {
                d[v]=d[u]+w;
                num[v] = num[u]+1;
                if(num[v]>=Nv)  //如果有Nv条边能够松弛v这个顶点（一个无自环的顶点，
                    return true;    //最多只有Nv-1条边与其相连—），那么一定出现了负环；
                    
                if(hs[v]==0)    //如果该顶点未在队列中，将其入队
                {
                    q.push(v);
                    hs[v]=1;
                }
            }
        }
        
    }
    
    return false;
}
 
int main()
{
    Read();
    
    if(SPFA(1))
        puts("Yes");
    else    
        puts("No");
    
    return 0;
    
}

解法二：Bellman_Ford 算法：

/**
 * 松弛定理：d[u]+w < d[v] ;
 * 
 * Bellman_Ford 算法：经过Nv-1 条边松弛，求得从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 一定是没有回路的，因为假设是正回路，那么去掉这条这条回路，一定
 * 能得到更短的距离，如果是负回路，那么一定得不到最短路；
 * 
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 * 
 * 对于要判断是否有负权回路这种情况，即要进行 Nv-1 轮所有边的松弛操作，可以不使用pre数组，
 * 因为进行Nv-1轮或者进行Nv轮迭代没什么区别，如果有负权值，那么进行Nv轮迭代以后边还是能够
 * 松弛；
*/
 
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
typedef pair<int,int> PII;
 
const int maxn = 2010 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
 
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
int Bellman_Ford(int st) //判断图中是否存在回路
{
    fill(d,d+maxn,INF);
    d[st]=0;
 
    for(int k=1;k<Nv;++k)
    {
        for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])
                    d[v]=d[u]+w;
            }
    }
 
    for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])   //还能被松弛，存在负回路
                    return 1; 
            }
 
    return 0; //不存在负回路
}
 
int main()
{
    Read();
 
    if(Bellman_Ford(1))
        puts("Yes");
    else
        puts("No");
 
    return 0;
 
}