队列优化Bellman-Ford算法

队列优化Bellman-Ford算法也叫SPFA算法，针对Bellman-Ford算法对不在源结点s出发的路径上的边的冗余扫描进行优化，使用注意事项：

(1)可以有负权边，但不能有负环

(2)适用于所有类型的图

存储结构采用邻接链表，n为顶点数，m为边数

int value[m], next[m], head[n], edge[m], d;

memset(head, -1, sizeof(head));

若源结点为顶点s，dis[i]标示顶点i到源结点s的最短距离（初始化dis[s]为0，其他为0x3f3f3f3f），vis[i]标示顶点i是否在队列中（0是在，1是不在，初始化为全0）

int dis[n], vis[n];

Bellman-Ford算法只对在源结点s出发的路径上的边进行松弛操作，使其满足三角形不等式，算法流程如下：

(1)队列开始只有源结点s

(2)取出队头t，扫描其所有出边(t, j, edge[i])，进行松弛操作（若dis[j] < dis[t] + edge[i]则用dis[t] + edge[i]更新dis[j]），同时若j不在队列中，将j入队

(2)重复上述步骤，直到队列为空

queue<int> q;
q.push(s);
vis[s] = 1;

while (!q.empty()) {
    auto t = q.front();
    q.pop();
    vis[t] = 0;

    for (int i = head[t]; i != -1; i = next[i]) {
        int j = value[i];
        if (dis[t] + edge[i] < dis[j]) {
            dis[j] = dis[t] + edge[i];

            if (!vis[j]) {
                q.push(j);
                vis[j] = 1;
            }
        }
    }
}

算法结束时，dis[i]存储顶点i到源结点s的最短距离，0x3f3f3f3f表明不可达（由于只对在源结点s出发的路径上的边进行松弛操作，若s和i不连通，dis[i]不会被更新，负权边也不影响）

注解：

(1)队列优化Bellman-Ford算法通常要好于朴素Bellman-Ford算法

(2)判断是否存在负环常用队列优化Bellman-Ford算法（虽然朴素Bellman-Ford算法也可以判断负环但一般不用）

cnt[i]标示源结点s到顶点i的最短路径的边数（初始化为全0）

int cnt[n];

开始要将所有结点入队；

取出队头，对出边进行松弛操作时，要同时更新最短路径的边数，边数达到上限就判断出有负环

bool MinusLoop() {
    queue<int> q;
    for (int i = 0; i < n; i++) {
        q.push(i);
        vis[i] = 1;
    }

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        vis[t] = 0;

        for (int i = head[t]; i != -1; i = next[i]) {
            int j = value[i];
            if (dis[j] > dis[t] + edge[i]) {
                dis[j] = dis[t] + edge[i];

                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;

                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }
    return false;
}

---