Bellman-Ford算法求解带负权的最短路径问题

发布于 / 数据结构与算法 / Comments Off on Bellman-Ford算法求解带负权的最短路径问题

0x00、Dijkstra并不是万能的

前面我们讲过了Dijkstra算法,Dijkstra算法可以很好的解决边权均为正数的最短路径问题,但是,请看下图:

(上面的点是A,左边的是B,右边的是C,作图的时候忘记打上去了TAT...)

如果我们使用Dijkstra来解决从A走向,我们的思路如下:

  1. 当前在A点,标记A已访问,设置MinDistance[B]= -1;MinDistance[C] = 1

  2. 因为MinDistance[B]最小,所以走到B,标记B已访问

  3. 当前在B,我们使用B去更新没有访问的邻接点,MinDistance[C] = -6

  4. 全部节点遍历完毕

此时MinDistance[B] = -1,但是我们知道,沿着路线A->C->B走,会得到更短的路线:-4,所以使用Dijkstra解得的答案是错误的

为了解决带有负权的最短路径问题,我们就需要学习Bellman-Ford算法。

0x01、三种不同的环

先引入三种环的定义:


将边权之和不同的环分别称为零环、正环、负环。在这里,零环和正环不会影响到我们最短路径的求解,因为如果是零环,我们走进去和没走进去是一样的,而正环走进去比不走进去的总路径长度还要多。只有负环才会有"走到环里比不走到环里的路径更短",所以我们只讨论负环。

与Dijkstra算法相同,我们准备一个数组MinDistance,存放该点到起点的最短路径。同时Bellman-Ford算法要返回一个bool类型的值,表示是否存在从起点可以到达的负环

在Bellman-Ford算法中,遍历是从起点到终点按照顺序进行遍历,而不是像Dijkstra那样定义visited数组(判断是否访问过该点)来判断是否应该遍历。

伪代码如下:

for(int i = 0; i < n - 1; i++){    //n为顶点数,进行n-1轮操作
    for(每一个从u->v的边){    //每一轮操作都要遍历每一条边
        if(d[u] + length[u->v] < d[v]){    //以u为中介点,可以使d[v]更小
            d[v] = d[u] + length[u->v];    //更新数组d里面的最短距离
        }
    }
}

此时,如果图中没有从起点可以到达的负环,则数组d中的所有值应该已经达到了最优。接下来我们判断是否存在起点可达的负环

判断是否存在从起点出发可以到达的负环,我们只需对所有变进行一轮遍历,判断是否存在某条边 u->v ,仍然满足d[u] + length[u->v] < d[v]。如果有,就说明图中存在从起点可以到达的负环。

for(每一个从u->v的边){
    if(d[u] + length[u->v] < d[v])
        return false;    //说明图中有源点可达的负环
}
return true;    //没有

这了Bellman算法的证明就不写了。。有兴趣的同学可以参考《算法笔记》这一节的讲解。。

0x02、C语言实现


由于Bellman-Ford算法需要遍历所有的边,所以使用邻接表会比较方便,代码如下:

struct Node{
    int v, dis;    //v为邻接边的目标顶点,dis为邻接边的边权
};

vector<Node> Adj[MAXV];    //图的邻接表
int n;    //顶点数
int d[MAXN];    //起点到各点的距离(MinDistance)

bool Bellman(int s){    //s为起点
    fill(d, d + MAXN, INF);    //初始化,INF为一个非常大的数
    d[s] = 0;    //起点到自身的距离为0
    
    //开始求解数组d
    
    for(int i = 0; i < n - 1; i++){    //执行n-1轮操作,其中n为顶点数
        for(int u = 0; u < n; u++){    //每轮操作遍历一遍所有的边
            for(int j = 0; j < Adj[u].size(); j++){   //遍历当前边的邻接边
                int v = Adj[u][j].v;    //v是当前边的邻接边的目标顶点
                int dis = Adj[u][j].dis;    //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;
}

转载原创文章请注明,转载自: 斐斐のBlog » Bellman-Ford算法求解带负权的最短路径问题
评论已关闭