Bellman–Ford algorithm

2018/08/13 ALGO

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

Shortest paths

An edge-weighted digraph is a digraph where we associate weights or costs with each edge. A shortest path from vertex s to vertex t is a directed path from s to t with the property that no other such path has a lower weight.

算法分析

Bellman-Ford算法是解决单源最短路径问题的一种算法,与Dijkstra算法类似的,Bellman-Ford是以松弛操作为基础,估计的最短路径值逐渐被更加准确的值代替,直至得到最优解。Bellman-Ford可以处理有向正负权非负环图,即最短路一定存在的图。相比较下Dijkstra不能处理带负权图,Bellman-Ford可以检测出图中是否带有负环。

假设一幅有向图G,包含n个节点、m条边。Bellman-Ford的思路是对全图进行n-1次松弛,每次遍历m条边更新最短路径的值。算法复杂度是O(nm)。下面是Bellman-Ford的伪代码:

// 初始化
for each vertex v in vertices:
    if v is source:
        distance[v] = 0
    else:
        distance[v] = infinity
// 松弛
for i in 1 to size(vertices)-1:
    for each edge(u,v) with weight w in edges:
        if distance[u] + w < distance[v]:
            distance[v] = distance[u] + w

发现问题

Bellman-Ford每一次松弛操作都是全图进行,也就是进行m次循环。但是这个过程中有很多松弛操作都是无用功,原因在于松弛操作生效于已经确定最短路的点和还没确定最短路的点之间的路径,全图操作的话意味着对那些已经确定了最短路的点继续进行松弛,这就浪费了很多时间。

上面的图例中,左上角的红点是已经确定了最短路的点,右下角的红点是还没确定最短路的点,而每次全图的松弛操作是发生在中间部分那些即将要确定最短路的点。因此使用队列数据结构可以优化Bellman-Ford算法,这种思路又叫做SPFA算法。

Shortest Path Faster Algorithm

SPFA算法本质上是Bellman-Ford算法的队列优化版本,是来自于西南交通大学段凡丁在1994年发表的论文。参见下图的SPFA示例,

Bellman-Ford Code

  1. 算法复杂度O(VE)
  2. 可以处理负权图
  3. 点的编号从1开始
  4. 没有负环回路则返回true
const int INF = 0x3f3f3f3f;
const int MAXN = 550;
int dist[MAXN];

struct Edge{
    int u, v;
    int cost;
    Edge(int _u = 0, int _v = 0, int _cost = 0):u(_u), v(_v), cost(_cost){}
};

vector<Edge>E;

bool bellman_ford(int start, int n){
    for(int i=1;i<=n;i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    for(int i=1;i<n;i++){
        bool flag = false;
        for(int j=0;j<E.size();j++){
            int u = E[j].u;
            int v = E[j].v;
            int cost = E[j].cost;
            if(dist[v] > dist[u] + cost){
                dist[v] = dist[u] + cost;
                flag = true;
            }
        }
        if(!flag)
            return true;
    }
    for(int i=0;i<E.size();i++){
        if(dist[E[j].v] > dist[E[j].u] + E[j].cost)
            return false;
    }
    return true;
}

SPFA Code

  1. 算法复杂度是不确定的,低于O(VE)
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0):v(_v), cost(_cost){}
};

vector<Edge>E[MAXN];

void addedge(int u, int v, int w){
    E[u].push_back(Edge(v.w));
}
bool vis[MAXN]; // 在队列标志
int cnt[MAXN]; // 每个点的入队列次数
int dist[MAXN];
bool SPFA(int start, int n){
    memset(vis, false, sizeof(vis));
    for(int i=1;i<=n;i++){
        dist[i] = INF;
    }
    vis[start] = true;
    dist[start] = 0;
    queue<int> que;
    while(!que.empty())
        que.pop();
    que.push(start);
    memset(cnt, 0, sizeof(cnt));
    cnt[start] = 1;
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i=0;i<E[u].size();i++){
            int v = E[u][i].v;
            if(dist[v] > dist[u] + E[u][i].cost){
                dist[v] = dist[u] + E[u][i].cost;
                if(!vis[v]){
                    vis[v] = true;
                    que.push(v);
                    // cnt用来判断是否存在负环回路
                    if(++cnt[v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

SPFA与BFS

仔细观察代码,会发现跟BFS十分类似。的确是这样的,SPFA的思路与BFS类似,从起点开始遍历离起点最近的点进行松弛。有些不同的是,BFS每次出队的点不会再进入,而SPFA每次出队的点有可能会重复进队,因为可能在图的扫描的后期有更好的最短路。SPFA中,如果某个点进队超过n次说明存在负环。

Search

    Table of Contents