简介

Bellman-Ford算法是求解单源最短路的算法之一，适用于可包含负边权的有向和无向图，可以判断是否包含负环（注意，如果是包含负权回路则不存在最短路问题）。时间复杂度 $O(nm)$ 。

Bellman-Ford算法

因为最短路径上最多有n-1条边，所以Bellman-Ford算法最多有n-1个阶段。在每一个阶段，我们对每一条边都要执行松弛操作。其实每实施一次松弛操作，就会有一些顶点已经求得其最短路，即这些顶点的最短路的“估计值”变为“确定值”。此后这些顶点的最短路的值就会一直保持不变，不再受后续松弛操作的影响(但是，每次还是会判断是否需要松弛)。在前k个阶段结束后，就已经找出了从源点出发“最多经过k条边”到达各个顶点的最短路。直到进行完n-1个阶段后，便得出了最多经过n-1条边的最短路。

核心代码如下：

 1int bellman(int s, int n, int m)
 2{
 3    dis[s] = 0;
 4    for(int k=1; k<n; k++){
 5        for(int i=1; i<=m; i++){
 6            dis[v[i]] = min(dis[v[i]], dis[u[i]]+w[i]);
 7        }
 8    }
 9    return 0;
10}

如果在n-1次松弛之后，还有可以进行松弛的边，那么就存在负环（负权回路）：

 1int bellman(int s, int n, int m)
 2{
 3    dis[s] = 0;
 4    for(int k=1; k<n; k++){
 5        for(int i=1; i<=m; i++){
 6            if(dis[u[i]]+w[i] < dis[v[i]]){
 7                dis[v[i]] = dis[u[i]]+w[i];
 8                pre[v[i]] = u[i];
 9            }
10        }
11    }
12    for(int i=1; i<=m; i++){
13        if(dis[u[i]]+w[i] < dis[v[i]]){
14            return -1;
15        }
16    }
17    return 0;
18}

SPFA

SPFA是Bellman-Ford算法的队列优化，核心思想，只有那些在前一遍松弛中改变了距离估计值的点，才可能引起它们的邻接点的距离估计值的改变。为什么队列为空就不改变了呢？就是因为要到下一点必须经过它的前一个邻接点。

设立一个先进先出的队列q用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

核心代码如下：

 1int spfa(int s, int n)
 2{
 3    dis[s] = 0; vis[s] = 1; q.push(s);
 4    while(!q.empty())
 5    {
 6        int u = q.front(); q.pop(); vis[u] = 0;
 7        for(int i=H[u]; ~i; i=e[i].next){
 8            int v = e[i].to, w = e[i].w;
 9            if(dis[u]+w < dis[v]){
10                dis[v] = dis[u]+w;
11                if(!vis[v]) q.push(v), vis[v] = 1;
12            }
13        }
14    }
15    return 0;
16}

其它优化

除了队列优化（SPFA）之外，Bellman-Ford 还有其他形式的优化，这些优化在部分图上效果明显，但在某些特殊图上，最坏复杂度可能达到指数级。

堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。

更多优化以及针对这些优化的 Hack 方法，可以看 fstqwq 在知乎上的回答。

模板

Bellman-Ford算法：

 1const int inf = 0x3f3f3f3f;
 2const int mxn = 1e3 + 5;
 3
 4int u[mxn], v[mxn], w[mxn];
 5int dis[mxn], pre[mxn];
 6
 7void bellman_init(int n)
 8{
 9    for(int i=1; i<=n; i++){
10        dis[i] = inf;
11        pre[i] = 0;
12    }
13}
14
15int bellman(int s, int n, int m)
16{
17    int k=0, f=1; dis[s] = 0;
18    while(f)
19    {
20        if(++k > n) return -1;
21        f = 0;
22        for(int i=1; i<=m; i++){
23            if(dis[u[i]]+w[i] < dis[v[i]]){
24                dis[v[i]] = dis[u[i]]+w[i];
25                pre[v[i]] = u[i];
26                f = 1;
27            }
28        }
29    }
30    return 0;
31}
32
33int main()
34{
35    int n, m;
36    scanf("%d %d", &n, &m);
37
38    for(int i=1; i<=m; i++)
39    {
40        scanf("%d %d %d", &u[i], &v[i], &w[i]);
41    }
42
43    bellman_init(n);
44    if(bellman(1, n, m) == -1)
45    {
46        printf("包含负权回路\n");
47    }
48    else
49    {
50        for(int i=1; i<=n; i++)
51            printf("%d ", dis[i]);
52        printf("\n");
53
54        for(int i=1; i<=n; i++)
55            printf("%d ", pre[i]);
56        printf("\n");
57    }
58
59    return 0;
60}
61
62/*
63Sample Input:
64
654 5
661 2 2
671 3 4
682 4 1
693 2 1
703 4 8
71
72
73Sample Output:
74
750 2 4 3
760 1 1 2
77
78*/

SPFA：

  1const int inf = 0x3f3f3f3f;
  2const int mxn = 1e3 + 5;
  3
  4struct E {
  5    int to, next, w;
  6} e[mxn];
  7
  8int H[mxn], tot;
  9
 10void add(int from, int to, int w) {
 11    e[tot] = {to, H[from], w};
 12    H[from] = tot++;
 13}
 14
 15void graph_init(int n)
 16{
 17    for(int i=1; i<=n; i++)
 18        H[i] = -1;
 19    tot = 0;
 20}
 21
 22int dis[mxn], pre[mxn], num[mxn];
 23bool vis[mxn];
 24queue<int> q;
 25
 26void spfa_init(int n)
 27{
 28    for(int i=1; i<=n; i++){
 29        dis[i] = inf;
 30        num[i] = pre[i] = 0;
 31    }
 32}
 33
 34int spfa(int s, int n)
 35{
 36    dis[s] = 0; q.push(s);
 37    num[s] = vis[s] = 1;
 38    while(!q.empty())
 39    {
 40        int u = q.front(); q.pop(); vis[u] = 0;
 41        for(int i=H[u]; ~i; i=e[i].next){
 42            int v = e[i].to, w = e[i].w;
 43            if(dis[u]+w < dis[v]){
 44                dis[v] = dis[u]+w;
 45                pre[v] = u;
 46                if(!vis[v]){
 47                    q.push(v), vis[v] = 1;
 48                    if(++num[v] > n) return -1;
 49                }
 50            }
 51        }
 52    }
 53    return 0;
 54}
 55
 56int main()
 57{
 58    int n, m;
 59    scanf("%d %d", &n, &m);
 60    graph_init(n);
 61
 62    for(int i=1; i<=m; i++)
 63    {
 64        int u, v, w;
 65        scanf("%d %d %d", &u, &v, &w);
 66        add(u, v, w);
 67    }
 68
 69    spfa_init(n);
 70    if(spfa(1, n) == -1)
 71    {
 72        printf("包含负权回路\n");
 73    }
 74    else
 75    {
 76        for(int i=1; i<=n; i++)
 77            printf("%d ", dis[i]);
 78        printf("\n");
 79
 80        for(int i=1; i<=n; i++)
 81            printf("%d ", pre[i]);
 82        printf("\n");
 83    }
 84
 85    return 0;
 86}
 87
 88
 89/*
 90Sample Input:
 91
 924 5
 931 2 2
 941 3 4
 952 4 1
 963 2 1
 973 4 8
 98
 99
100Sample Output:
101
1020 2 4 3
1030 1 1 2
104
105*/

简介#

Bellman-Ford算法#

SPFA#

其它优化#

模板#

简介

Bellman-Ford算法

SPFA

其它优化

模板