数据结构-图的遍历之Bellman-Ford算法和SPFA算法

一、Bellman-Ford算法

1. 用于解决单源最短路径的问题，但也能够处理有负权边的情况。这是与Djikstra算法不同的地方。
2. 关于复杂度，要比Djikstra的复杂度更高一点。O(VE),而Djikstra复杂度是O(V^2),V是点的数量，E是边的数量
3. 原理，就是会出现负环的情况，会使得最短路径越来越小，进而产生错误；如果出现负环，源点无法到达，那么也是不会影响求解的。
4. 设置d数组，用于存储最短路径的距离，如果存在可以到达的负环，那么返回false；如果不存在，那么数组d中存储的就是最短距离，返回true。
5. 主要思想及伪代码：就是对于图中的边进行V-1轮操作。每一轮遍历所有的边，如果可以更新当前的距离，那么就进行更新；此时如果没有从源点到达的负环，那么数组d就是当前最优值，因此只需再对于所有边进行遍历一次，判断是否还有值可以更新，如果有，那么就说明图中存在源点可以到达的负环，返回false，如果没有那就返回true。
6. 使用邻接表，如果使用邻接矩阵会使得算法的复杂度达到O(V^3)代码：

struct node{
    int v, dis;//v为邻接边的目标顶点，dis为邻接边的边权
};
vector<node> Adj[MAXN];
int n;
int d[MAXN];

bool Bellman_Ford(int s){
    fill(d, d+MAXN; INF);
    d[s] = 0;
    for(int i = 0; i < n-1; i++){
        for(int u = 0; u < n; u++){
            for(int j = 0; j < Adj[u].size(); j++){
                int v = Adj[u][j].v;
                int dis = Adj[u][j].dis;
                if(d[u] + dis < d[v]){
                    d[v] = d[u] + dis;
                }
            }
        }
    }
    //以下为判断负环的代码
    for(int u = 0; u < n; u++){
        for(int j = 0; j < Adj[u].size(); j++){
            int v = Adj[u][j].v;
            int dis = Adj[u][j].dis;
            if(d[u] + dis < d[v]){
                return false;
            }
        }
    }
    return true;
}

• 需要注意点：统计最短路径条数的做法，由于Bellman-Ford算法期间会多次访问曾经访问过的结点，如果还是按照之前的写法，会统计已经出现过的结点，为了解决这个问题，使用记录 前驱结点的数组为set pre[MAXN],当遇见一条和已有最短路径长度相同路径时，必须重新计算最短路径的条数。

二、SPFA（Shortest Path Faster Algorithm）算法

1. 这是对Bellman-Ford优化后产生的算法
2. 我们知道每轮都需要操作每条边，其中存在很多无意义的边，所以我们知道只有当某个顶点的d[u]值发生改变的时候，从它出发的邻接点v的d[v]值才会发生改变
3. 由此，可以进行优化，建立一个队列，每次将队首顶点u取出，然后对从u出发的所有边u->v进行松弛操作，如果没有获得最优的值就不管，如果获得最优值，v如果不在队列中，那么就添加进入队列。这样操作直到队列中没有结点（说明图中没有从源点可达的负环）， 或是某个顶点的入队次数超过V-1（说明图中存在从源点可达的负环）。
4. 这种优化后的算法期望时间复杂度是O(kE),k是一个图的常数，E是图的边数。但是如果图中存在源点可以到达的负环，那么传统的SPFA的时间复杂度退化成O(VE)。
5. 如果事先知道图中不会有环，那么num数组的部分可以去掉。
6. 如果负环从源点不可达，则需要添加辅助顶点C，并添加一条从源点到达C的有向边以及V-1条从C到达除源点外各顶点的有向边才能判断负环是否存在。思考为啥

• 下面给出SPFA的代码：

struct node{
    int v, dis;//v为邻接边的目标顶点，dis为邻接边的边权
};
vector<node> Adj[MAXN];
int n, d[MAXN], num[MAXN];//num数组为记录顶点入队列次数
bool inq[MAXV];//顶点是否在队列中

bool SPFA(int s){
    //初始化
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d+MAXN, INF);
    //源点入队列部分
    queue<int> Q;
    Q.push(s);
    inq[s] = true;
    num[s]++;
    d[s] = 0;
    //主体部分
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        //遍历u所有邻接边v
        for(int j = 0; j < Adj[u].size(); j++){
            int v = Adj[u][j].v;
            int dis = Adj[u][j].dis;
            //松弛操作
            if(d[u] + dis < d[v]){
                d[v] = d[u] + dis;
                if(!inq[v]){
                    Q.push(v);
                    inq[v] = true;
                    num[v]++;
                    if(num[v] >= n) return false;
                }
            }
        }
    }
    return true;
}