首页 > 图论 > 最短路径 > Bellman-Ford最短路径算法
2014
06-06

Bellman-Ford最短路径算法

单源最短路径:给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。
关于这个问题我们已经讨论了迪杰斯特拉算法。
Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,
Bellman-Ford适合这样的图。在网络路由中,该算法会被用作距离向量路由算法。
Bellman-Ford也比迪杰斯特拉算法更简单和同时也适用于分布式系统。但Bellman-Ford的时间复杂度是O(VE),E为边的个数,这要比迪杰斯特拉算法慢。
算法描述
输入:图 和 源顶点src
输出:从src到所有顶点的最短距离。如果有负权回路(不是负权值的边),则不计算该最短距离,
没有意义,因为可以穿越负权回路任意次,则最终为负无穷。

算法步骤:

1.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ← +∞, d[s] ←0;
2.迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)
3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d[v]中。

关于该算法的证明也比较简单,采用反证法,具体参考:http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf
该算法是利用动态规划的思想。该算法以自底向上的方式计算最短路径。
它首先计算最多一条边时的最短路径(对于所有顶点)。然后,计算最多两条边时的最短路径。外层循环需要执行|V|-1次。
例子
一下面的有向图为例:给定源顶点是0,初始化源顶点距离所有的顶点都是是无穷大的,除了源顶点本身。因为有5个顶点,
因此所有的边需要处理4次。

Example Graph
按照以下的顺序处理所有的边:(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D).
第一次迭代得到如下的结果(第一行为初始化情况,最后一行为最终结果):

当 (B,E), (D,B), (B,D) 和 (A,B) 处理完后,得到的是第二行的结果。
当 (A,C) 处理完后,得到的是第三行的结果。
当 (D,C), (B,C) 和 (E,D) 处理完后,得到第四行的结果。

第一次迭代保证给所有最短路径最多只有1条边。当所有的边被第二次处理后,得到如下的结果(最后一行为最终结果):

第二次迭代保证给所有最短路径最多只有2条边。我们还需要2次迭代(即所谓的松弛操作),就可以得到最终结果。

C/C++实现如下:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
using namespace std;
//表示一条边
struct Edge
{
    int src, dest, weight;
};

//带权值的有向图
struct Graph
{
    // V 顶点的数量, E 边的数量
    int V, E;

    // 用边的集合 表示一个图
    struct Edge* edge;
};

// 创建图
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

    return graph;
}

// 打印结果
void printArr(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// 获得单源最短路径,同时检测 负权回路
void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[V];

    // 第一步初始化
    for (int i = 0; i < V; i++)
        dist[i]   = INT_MAX;
    dist[src] = 0;

    // 第二步:松弛操作
    for (int i = 1; i <= V-1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // 第三步: 检测负权回路.  上面的操作保证没有负权回路的存在,
    // 如果找到了更短的路径,则说明存在负权回路
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] + weight < dist[v])
            printf("Graph contains negative weight cycle");
    }

    printArr(dist, V);
    return;
}

// 测试
int main()
{
    /* 创建 例子中的那个图的结构 */
    int V = 5;
    int E = 8;
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 (or A-B in above figure)
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    // add edge 0-2 (or A-C in above figure)
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    // add edge 1-2 (or B-C in above figure)
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    // add edge 1-3 (or B-D in above figure)
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    // add edge 1-4 (or A-E in above figure)
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    // add edge 3-2 (or D-C in above figure)
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    // add edge 3-1 (or D-B in above figure)
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    // add edge 4-3 (or E-D in above figure)
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    BellmanFord(graph, 0);

    return 0;
}

参考:http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }