SPFA算法

SPFA算法的浅要理解

思路

对Bellman-Ford进行优化，松弛操作的产生是因为

dist[b] = min(dist[b], dist[a] + w);

dist[a] 在之前的松弛操作中发生了改变，导致 dist[b] 在该次松弛中也需要改变 所以可以使用队列的方式将因松弛发生改变的点放入队头 每次将队头弹出并将与之相连的点进行松弛操作，松弛成功后更新队头 直到队列为空 注：需要一个st[N]数组来记录哪些点已经在队列中，防止重复

代码

int spfa()
{
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    else
        return dist[n];
}

增：

SPFA判负环只需要添加一个 cnt[N] 数组，每次进行松弛操作时增加如下操作

cnt[j] = cnt[t] + 1; //cnt[j]代表从第1个点到第j个点经过了多少个点

当然一开始的队头需要将所有点都放入，因为负环可能不在1点开始的路径上 如果 cnt[j] >= n 时，由于共n个点，抽屉原理可知存在负环

代码

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n)
                    return false;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return true;
}