SPFA算法

SPFA可以理解为bellman_ford算法的堆优化版，在每一次的查询中，可以发现新更新的点的路径一定是这条新的路径上有上一次更新的点，所以才会有新的更新，如果一个点更新了就把它加入队列中，就不用遍历全部的边去更新了。优化后就不能求限制边数的最短路了。

SPFA算法思路与bellman_ford十分接近，但是代码与dijkstra算法十分相似，一般来说SPFA的速度没有dijkstra快，但是SPFA可以求带负边的图的最短路。

一般在图论问题中，如果是没有负边的单源最短路，用dijkstra算法，带负边用SPFA，限制边数用bellman_ford，多源最短路用Floyd算法，有负环就无解。

SPFA求单源最短路

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], e[maxn], w[maxn], ne[maxn], idx;
int n, m;
int dist[maxn];
bool vis[maxn];     // 标记队列里面有没有这个点，有的话就不加进去了。
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
void spfa()
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    queue<int> heap;
    dist[1] = 0;
    heap.push(1);
    while (heap.size())
    {
        auto t = heap.front();
        heap.pop();
        vis[t] = 0;     // 已经弹出这个点了，队列里没有了。
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int x = t, y = e[i], s = w[i];
            if (dist[y] > dist[x] + s)
            {
                dist[y] = dist[x] + s;
                if (!vis[y])    // 如果队列没有就不用加进队列了，因为之后会搜索这个点。
                {
                    heap.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}

SPFA判断负环

如果出现负环，那么求解最短路时就会出现这个环中的几条边循环进行计算，正常情况下的最短路边数一定不会超过n条边，那么就可以定义一个数组去记录到这个点的路径出现了多少条边。如果边数超过了n，就说明出现了负环。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], e[maxn], w[maxn], ne[maxn], idx;
int cnt[maxn];
int vis[maxn];
int dist[maxn];
int n, m;
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool spfa()
{
    queue<int> heap;
    for (int i = 1; i <= n; i++)
    {
        heap.push(i);
    }
    while (heap.size())
    {
        auto t = heap.front();
        heap.pop();
        vis[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int a = t, b = e[i], c = w[i];
            if (dist[b] > dist[a] + c)
            {
                dist[b] = dist[a] + c;
                cnt[b] = cnt[a] + 1;
                if (cnt[b] > n) return true;
                if (!vis[b])
                {
                    vis[b] = true;
                    heap.push(b);
                }
            }
        }
    }
    return false;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}