shortest path algorithm —— Bellman–Ford

Posted on Edited on Views:

Bellman–Ford

Bellman–Ford 算法是一种单源最短路径算法，用于计算一个顶点到其他所有顶点的最短路径。

算法思想

Bellman–Ford 算法的基本思想是：就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

松弛操作(relaxation)：松弛操作是指对于一条边e，我们试图通过这条边来缩短起点到终点的距离。如果dis[a] + w < dis[b]，那么我们就可以通过这条边来缩短起点到终点的距离，即dis[b] = dis[a] + w。

算法步骤

  1. 初始化：创建一个一维数组dis，用于存储起点到各点的最短路径长度，初始化为无穷大，起点到自己的距离为0。

  2. 循环：对图上所有的边进行n-1轮松弛操作。

  3. 判断负环：如果第n轮仍然有松弛操作，说明图中存在负环。

  4. 返回结果：dis[i]即为起点到终点的最短路径长度。

    为什么第二步是n-1轮松弛操作？

    因为最短路径最多包含n-1条边，所以进行n-1轮松弛操作后，所有的最短路径都会被计算出来。

    如果第二步是n轮松弛操作，那么就无法判断负环，因为负环的最短路径包含n条边，所以进行n轮松弛操作后，负环的最短路径长度仍然会被更新。

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
struct Edge {
    int a, b, w; // 边的起点、终点、权重
} edges[m];

int main{
    int n, m; // n个顶点，m条边
    cin >> n >> m; 
    int dis[n]; // dis[i]表示起点到顶点i的最短路径长度
    
    // 初始化
    memset(dis, 0x3f, sizeof(dis)); // 初始化为无穷大
    dis[0] = 0; // 起点到自己的距离为0

    // 读入边
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
        dis[b] = min(dis[b], dis[a] + w); // 松弛操作
        // dis[a] = min(dis[a], dis[b] + w); // 无向图
    }

    // 循环
    for (int i = 0; i < n - 1; i++) { // 进行n-1轮松弛操作
        for (int j = 0; j < m; j++) { // 对图上所有的边进行松弛操作
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dis[b] = min(dis[b], dis[a] + w); // 松弛操作
            // dis[a] = min(dis[a], dis[b] + w); // 无向图
        }
    }

    // 判断负环
    bool flag = false;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (dis[b] > dis[a] + w) {
            flag = true;
            break;
        }
    }
    if (flag) cout << "此图存在负环" << endl;

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << dis[i] << " ";
    }
}

复杂度分析

  • 时间复杂度：$O(nm)$

    每一轮循环中，我们对图上所有的边都进行了一次松弛操作，所以总共进行了n-1轮循环，每一轮循环中，我们对图上所有的边都进行了一次松弛操作，所以总共进行了m次松弛操作，所以时间复杂度为$O(nm)$。

  • 空间复杂度：$O(n)$

    我们只需要一个一维数组dis来存储起点到各点的最短路径长度，所以空间复杂度为$O(n)$。

队列优化（SPFA）

队列优化的 Bellman–Ford 算法又称为 SPFA（Shortest Path Faster Algorithm），是对 Bellman–Ford 算法的一种优化。

SPFA 算法的基本思想是：在 Bellman–Ford 算法中，我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，但是实际上，只有那些在上一轮循环中被松弛过的边，才有可能在这一轮循环中继续被松弛。所以我们可以用一个队列来存储这些在上一轮循环中被松弛过的边，这样就可以减少不必要的松弛操作。

算法步骤

  1. 初始化：创建一个一维数组dis，用于存储起点到各点的最短路径长度，初始化为无穷大，起点到自己的距离为0。
  2. 循环：将起点加入队列，对队列中的每一条边进行松弛操作，如果松弛成功，就将这条边的终点加入队列。
  3. 判断负环：如果某个顶点入队次数超过n次，说明图中存在负环。
  4. 返回结果：dis[i]即为起点到终点的最短路径长度。
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
struct Edge {
    int a, b, w; // 边的起点、终点、权重
    int ne; // 链表中的下一条边
} edges[m];

int h[N], e[M], w[M], ne[M], idx; // 链表的头结点、边的起点、终点、权重、下一条边、边的编号
int main{
    int n, m; // n个顶点，m条边
    cin >> n >> m; 
    int dis[n]; // dis[i]表示起点到顶点i的最短路径长度
    bool st[n]; // st[i]表示顶点i是否在队列中
    
    // 初始化
    memset(dis, 0x3f, sizeof(dis)); // 初始化为无穷大
    dis[0] = 0; // 起点到自己的距离为0

    // 循环
    queue<int> q;
    q.push(0); // 将起点加入队列
    st[0] = true; // 起点已经在队列中
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false; // 将t从队列中取出
        for (int i = h[t]; i != -1; i = ne[i]) { // 对队列中的每一条边进行松弛操作
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) { // 松弛操作
                dis[j] = dis[t] + w[i];
                if (!st[j]) { // 如果松弛成功，就将这条边的终点加入队列
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    // 判断负环
    bool flag = false;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (dis[b] > dis[a] + w) {
            flag = true;
            break;
        }
    }
    if (flag) cout << "此图存在负环" << endl;

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << dis[i] << " ";
    }
}

复杂度分析

  • 时间复杂度：$O(nm)$

    每一轮循环中，我们对队列中的每一条边都进行了一次松弛操作，所以总共进行了m次松弛操作，所以时间复杂度为$O(nm)$。

  • 空间复杂度：$O(n)$

    我们只需要一个一维数组dis来存储起点到各点的最短路径长度，一个一维数组st来存储顶点是否在队列中，所以空间复杂度为$O(n)$。