LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

    

   什么是Bellman-Ford算法?Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行,可以解决负权边的问题。

    Bellman-Ford算法的核心代码只有四行,如下

for(k=1; k<=n-1; k++)

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            dis[v[i]] = dis[u[i]] + w[i];

    Bellman-Ford算法的核心代码意思是:遍历每一个点,其中每一次遍历时,遍历所有的边,对每个边进行一次松弛操作。

    松弛什么?请点击查看。算法十一:Dijkstra算法 - 一个点到各个点的最短路径

    现在有如下图,共5个点5条边,边都是有向边,其中点1到点2的距离为负数。如下:

无标题.jpg


    为什么会进行n-1次的循环呢?因为在不包含负权回路的路径中,n个点最多有n-1条边。在负权边中,负权回路会使最短路径不断的变小,永无止境。

完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10];

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

            }

        }

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

    Bellman-Ford算法的时间复杂对为O(MN)。

    我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路,那么我们需要检测图中是否包含负权回路:

sign = 0

for(i=1; i<=m; i++)

    if(dis[v[i]] > dis[u[i]] + w[i])

        flag = 1;

if(sign == 1)

    printf("此图有负权回路");

    另外,在n-1轮循环中,若n-3轮已经松弛完毕,那么n-2和n-1两次循环便毫无意义,因此增加判断,若第x轮dis数组已经不再发生变化了,则不在继续进行循环。

    新版的完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        //本轮dis数组是否发生变化

        ckeck = 0;

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

                check = 1;

            }

        }

        //本轮没有发生松弛,则不再继续进行了。

        if(ckeck == 0){

            break;

        }

    }

    sign = 0

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            sign = 1;

    if(sign == 1){

        printf("此图有负权回路");

    }else{

        for(i=1; i<=n; i++){

            printf("%d ", dis[i]);

       }

    }

    return 0;

}



    在第每一轮循环中,其实只对上一次发生了松弛的边的相邻边判断是否需要松弛,因此,没有必要每次都进行m次循环(遍历所有的边判断是否需要松弛)。比如第一轮松弛了1->2和1->5,那么第二次仅仅判断2->3和5->4这两个边是否需要松弛,而不需要遍历所有的边。

    在这种情况下,我们引入队列,将需要松弛的点加入队列。每个点仅仅需要入队一次即可,因为入队多次是没有意义的。初始时我们将1号点(源点)加入队列。然后开始遍历队列,对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然,在最坏的情况下,和Bellman-Ford算法的时间复杂度是一样的,即O(MN)。此优化也可以解决负权边。

    完整代码如下:

#include <stdio.h>

int main(){

    int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];

    int book[10] = {0};

    //first数组和next数组用来建立领接表,即first记录一个边的开头,比如第2号边的开头是点a,那么first[a]=2,a开头的下一个边是第5号边,则next[5]=a,组成一个链表的形式

    int first[10], next[10];

    int queue[100] = {0}, head = 1, tail = 1;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    //book用来标记那个点已经入队了,因为队列中同时出现同一个点多次是没有意义。

    //first用来标记第i条边的起点

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

        book[i] = 0;

        first[i] = -1;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

        //使用first和next两个数组建立领接表

        next[i] = first[u[i]];

        first[u[i]] = i;

    }

    //源点入队

    queue[tail] = start;

    tail++;

    //标记已经入队的点

    book[i] = start;

    while(head < tail){

        //当前需要处理的点,是队首的点,处理队首开头的所有边

        k = first[queue[head]];

        //扫描这个点开头的所有边

        while( k != -1){

            if(dis[v[k]] > dis[u[k]] + w[k]){

                dis[v[k]] = dis[u[k]] + w[k];

                if(book[v[k]] == 0){

                    queue[tail] = v[k];

                    tail++;

                    book[v[k]] = 1;

                }

            }

            k = next[k];

        }

        //这个点开头的所有边都处理完了,就出队

        book[queue[head]] = 0;

        head++;

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    getchar();getchar();

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

Ps:本算法参考《啊哈!算法》一书。

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号