8 Bellman Ford算法&SPFA

图论 —— 最短路 —— Bellman-Ford 算法与 SPFA_通信网理论基础 分别使用bellman-ford算法和dijkstra算法的应用-CSDN博客

图解Bellman-Ford计算过程以及正确性证明 - 知乎 (zhihu.com)

语雀版本

1 概念

**适用场景：**单源点，可以有负边，不能有负权环。

**dis(v)：**源点s到v的距离。初始话dis(s)=0,其余为无穷大。

**n：**顶点数

**m：**边数

复杂度O(mn)：对边进行n-1次遍历。如果dis(v)>dis(u)+e(u,v)，则更新dis(v)=dis(u)+e(u,v)

**合理性：**基于这个方式，每次遍历起码有一个点的dis(v)是得到最优值。所以遍历n-1次就够了。

负权环：环的权值和为负。如果按上述的方式遍历，很有可能会导致某个点的dis值经过环之后变得更小。重复遍历后越来越小。

**判断负权环：**三角不等式。无负权环时，n-1次后所有dis都是最优。如果有，则会导致得不到最小dis。基于这一点，可以在n-1次后，再遍历一次，如果还存在dis(v)>dis(u)+e(u,v)，则有负权环。

2 实现

2.1 n-1次遍历

void Bellman_Ford()
{
    for(int i=0;i<n;i++) 
        dis[i]=INF;
    dis[0]=0;
 
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m;j++)//枚举所有边
        {
            int x=u[j];//边j的起点
            int y=v[j];//边j的终点
            if(dis[x]<INF)//松弛
                dis[y]=min(dis[y],dis[x]+w[j]);
        }
}

2.2 第n次变量——三角布不等式判断环

void Bellman_Ford()
{
    for(int i=0;i<n;i++) 
        dis[i]=INF;
    dis[0]=0;
 
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m;j++)//枚举所有边
        {
            int x=u[j];//边j的起点
            int y=v[j];//边j的终点
            if(dis[x]<INF)//松弛
                dis[y]=min(dis[y],dis[x]+w[j]);
        }
    for(int j=1;j<=m;j++)//枚举所有边
        {
            int x=u[j];//边j的起点
            int y=v[j];//边j的终点
            if(dis[y]>dis[x]+w[j])//
                cout<<"有负权环";
                return;
        }
}

3 SPFA-基于队列的优化

SPFA：Shortest Path Faster Algorithm。用队列来记录待遍历的点，每次不遍历所有边，只遍历和改点相邻的边。

3.1 实现

struct Edge{
    int to,dis;
};
vector<Edge> edge[N];
bool vis[N];
int dis[N];
void SPFA(int s) {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    dis[s] = 0;
    
    deque<int> Q;
    Q.push_back(s);
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop_front();
        vis[x] = 0;
        for (int i = 0; i < edge[x].size(); i++) {
            int y = edge[x][i].to;
            if (dis[y] > dis[x] + edge[x][i].to) {
                dis[y] = dis[x] + edge[x][i].to;
                if (!vis[y]) {
                    vis[y] = true;
                    if (!Q.empty() && dis[y] < dis[Q.front()])//加入队首
                        Q.push_front(y);
                    else//加入队尾
                        Q.push_back(y);
                }
            }
        }
    }
}

3.2 判断负环-判断每个点进队列的次数（大于n）

struct Edge {
    int from, to;
    int dis;
    Edge() {}
    Edge(int from, int to, int dis) : from(from), to(to), dis(dis) {}
};
struct SPFA {
    int n, m;
    Edge edges[N]; //所有的边信息
    int head[N];   //每个节点邻接表的头
    int next[N];   //每个点的下一条边
    int pre[N];    //最短路中的上一条弧
    bool vis[N];
    int dis[N];
    int cnt[N]; //进队次数
 
    void init(int n) {
        this->n = n;
        this->m = 0;
        memset(head, -1, sizeof(head));
    }
 
    void AddEdge(int from, int to, int dist) {
        edges[m] = Edge(from, to, dist);
        next[m] = head[from];
        head[from] = m++;
    }
 
    bool negativeCycle(int s) { //判负环
        memset(vis, false, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;
 
        queue<int> Q;
        Q.push(s);
 
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = false;
            for (int i = head[x]; i != -1; i = next[i]) {
                Edge &e = edges[i];
                if (dis[e.to] > dis[x] + e.dis) {
                    dis[e.to] = dis[x] + e.dis;
                    pre[e.to] = i;
                    if (!vis[e.to]) {
                        vis[e.to] = true;
                        Q.push(e.to);
                        if (++cnt[e.to] > n)
                            return true;
                    }
                }
            }
        }
        return false;
    }
} spfa;
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        spfa.init(n);
        int S;
        scanf("%d", &S);
        for (int i = 1; i <= m; i++) {
            int x, y, dis;
            scanf("%d%d%d", &x, &y, &dis);
            //无向边添边两次
            spfa.AddEdge(x, y, dis);
            spfa.AddEdge(y, x, dis);
        }
        spfa.negativeCycle(S);
        for (int i = 1; i <= n; i++)
            printf("%d\n", spfa.dis[i]);
    }
    return 0;
}