Bellman-Ford算法概述

此算法由理查德·贝尔曼和小莱斯特·伦道夫·福特创立,是求解单源最短路径问题的一种算法.其原理是对图进行n-1次(轮)松弛操作,其中n是图中点的个数.不断地松弛,逐渐逼近最优解,最终得到最短路径长度.

相对于Dijkstra算法,其优点是可以处理有负边权的图,并且实现简单.缺点是时间复杂度过高,高达O(n*m),其中n,m分别为图的点,边数.不过,此算法可以进行若干种优化来提高效率.

算法描述

算法过程

  1. 读取图的点数,边数–n,m;和起点s

  2. 初始化一个dis[]数组,其中dis[i]代表s到i的最短路径长度,除了dis[s]为0,其余设置为无穷大

  3. 进行n-1次循环,在每次循环中遍历所有的m条边,尝试使用每条边<ui,vi,wi>松弛,即判断

    dis[vi]>dis[ui]+wi

    是否成立,如果成立则更新dis[vi],即为所谓的松弛操作.

  4. 当第3步的循环结束后,dis[]中即为最终结果.

算法分析

参考自https://blog.csdn.net/Africa_South/article/details/90299584

思想分析

尽管此算法和Dijkstra算法都基于松弛操作,但是与Dijkstra算法基于的贪心思想不同,此算法基于动态规划的思想.

首先,一个n个点的图,则所有的最短路最多只有n-1条边,否则如果有n条边以上的边,则说明有回路(参考最小生成树).

那么如果使用d(v,k)代表从源点s到点v,且最多含有k条边的最短路径长度.所以d(v,n-1)就是我们期望的最终状态.

Bellman-Ford算法的初始状态(k=0):

d(v,0)={0,v=s∞,v≠sd(v,0) = \begin{cases} 0, & \text v=s \\ \infty , & \text v\neq s \\ \end{cases}

对1<=k<=n-1,有:

d(v,k)=min{d(u,k−1)+w(u,v)∣u是v的前驱顶点}d(v,k)=min\{d(u,k−1)+w(u,v)∣u是v的前驱顶点\}

因此要求s->v的最短路,可以先求出s->u的最短路.

根据状态转移方程,我们可以按照

d(*,1),d(*,2),d(*,3),...,d(*,n-1)

这样的顺序逐步计算.

伪代码

用dis[v]做为s->v的最短路径.

1
2
3
4
5
6
7
8
init dis[]:
    dis[*] = 无穷大
    dis[s] = 0
for(int k = 1;k <= n-1;++k){
    for((u,v,w) in 所有的边){
        d[v] = min(d[v],d[u]+w);
    }
}

关键点

  1. 对于外层进行的n-1次循环,可以认为第i次循环结束后,dis[*]代表使用了i条边能达到的最短路径.n-1次循环后,代表使用n-1条边能够达到的最短路径.

  2. 换个角度,由于最短路至多有n-1条边,所以我们进行的每一次循环都至少确定一个点的最短路径.n-1次循环后,确保除了s外(它是起点),剩余的n-1个点的最短路径全部求得.

至于第2点,这篇文章中有较好的讲解.

第2点中的至少需要注意,一轮循环不一定只确定一个点的最短路径.

负权边与负权环的判断

Dijkstra算法的贪心策略基于深度进行搜索,而Bellman-Ford算法则基于广度进行搜索.

因此,Bellman-Ford算法可以对负权边进行操作.

另一方面,由于只需要n-1轮松弛操作便可保证求出最短路径,那么如果发现再多进行第n轮松弛仍然可以缩短路径长度,则可以判定该图一定存在负权环.

注意:有负权边不代表一定有负权环.

时间复杂度

由于需要进行n-1轮松弛,每轮都需要遍历所有的m条边,因此时间复杂度为O(n*m)

代码实现

本代码使用C语言,采用邻接矩阵存图.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int **graph;
    int n, m;
    int start;
} Graph;

void init_graph(Graph *graph) {
    scanf("%d%d", &graph->n, &graph->m);
    scanf("%d", &graph->start);

    graph->graph = (int **)malloc(sizeof(int *) * (graph->n + 1));
    for (int i = 0; i <= graph->n; ++i)
        graph->graph[i] = (int *)malloc(sizeof(int) * (graph->n + 1));

    for (int i = 0; i <= graph->n; ++i) {
        for (int j = 0; j <= graph->n; ++j) {
            graph->graph[i][j] = 0;
        }
    }

    for (int i = 0; i < graph->m; ++i) {
        int from, to, w;
        scanf("%d%d%d", &from, &to, &w);
        graph->graph[from][to] = w;
    }
}

int* bellman_ford(Graph *graph) {
    int *dis = (int *)malloc(sizeof(int) * (graph->n + 1));

    for (int i = 1; i <= graph->n; ++i)
        dis[i] = 0x7FFFFFFF;

    dis[graph->start] = 0;

    // 最外层循环进行n-1轮松弛操作
    for (int k = 1; k <= graph->n - 1; ++k) {
        for (int i = 1; i <= graph->n; ++i) {
            for (int j = 1; j <= graph->n; ++j) {
                if (graph->graph[i][j] != 0 && dis[j] > dis[i] + graph->graph[i][j]) {
                    dis[j] = dis[i] + graph->graph[i][j];
                }
            }
        }
    }

    return dis;
}

int main() {
    Graph graph;
    init_graph(&graph);
    int *dis = bellman_ford(&graph);

    for (int i = 1; i <= graph.n; ++i) {
        printf("%d ", dis[i]);
    }

    for (int i = 0; i <= graph.n; ++i)
        free(graph.graph[i]);
    free(graph.graph);
    free(dis);

    return 0;
}