$\Huge\color{orchid}{点击此处获取更多干货}$

SPFA

SPFA原理在此

之前在Bellman-Ford算法部分说过，最短路求解时，最多松弛$(n-1)$轮即可求出最短路，如果在第$n$轮时仍然存在着松弛成功的可能，就说明图中存在负权回路，至于为什么，可以先来关注一下，负权回路上的每个节点，在松弛操作执行过程中发生了什么：

显而易见，沿着负权回路2->3->4->5->2（权值之和为-2）执行松弛的过程中，回路上每一个节点及其后继节点的最短距离，每走一圈就对应减少2，并且可以一直无限减少下去，其中的每个节点都会无限次的出入队列。换句话说，环上每个节点都需要无限的等待其前驱节点更新完毕，这点很像数据库和操作系统中经常被提到的“死锁”(deadlock)
没有负权回路的时候，一个节点最多执行松弛$(n-1)$次。在求最短路的基础上，还可以对每个节点上松弛执行成功的次数加以统计，一旦发现了某个节点松弛成功次数达到了$n$，就可以判断当前存在死锁（进入了负权回路）

C++ 代码

bool LinkGraph::isDeadlocked() {
    vector<int> dists(numVex + 1),      //距离
                cnt(numVex + 1),        //松弛次数
                inQueue(numVex + 1);    //是否在队列中
    queue<int> q;
    //不保证图连通，每个节点都可能成为负权回路入口
    for (int i = 1; i <= numVex; i++) {
        inQueue[i] = 1;
        q.push(i);
    }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        inQueue[cur] = 0;
        for (int i = last[cur]; i != 0; i = prev[i]) {
            int nx = fin[i];
            if (dists[nx] > dists[cur] + val[i]) {
                dists[nx] = dists[cur] + val[i];
                cnt[nx] = cnt[cur] + 1;//这里的松弛次数对应的是Bellman-Ford算法中的松弛次数
                if (cnt[nx] >= numVex) { //第n次松弛仍然存在成功可能性，就说明存在负权回路
                    return true;
                }
                if (!inQueue[nx]) {
                    inQueue[nx] = 1;
                    q.push(nx);
                }
            }
        }
    }
    return false;
}