数据结构-图的遍历之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;
}
上一篇:Leetcode 323: Number of Connected Components in an Undirected Graph


下一篇:@codeforces - 1097G@ Vladislav and a Great Legend