Next Topic

单源最短路径(Bellman-Ford算法）

数据结构与算法第五章图(gragh) 单源最短路径(Bellman-Ford算法）

算法对所有边进行多轮松弛(relaxation)，求得最短路径。
算法可以处理有负权边(无负权环)的有向图。
如果是有向图中有负权环或无向图中有负权边，则无法计算最短路径。

Relaxation means updating the shortest distance to a node if a shorter path is found through another node.

1. 核心原理

Bellman-Ford 的核心思想是动态松弛：
通过逐步松弛所有边，迭代更新从源点到其他节点的最短距离。

松弛操作（Relaxation）：
对于边 u → v，检查是否可以通过 u 缩短到达 v 的路径，即：
if dist[v] > dist[u] + weight(u, v), 则更新 dist[v] = dist[u] + weight(u, v)。
迭代次数：
对图中的所有边进行 V-1 次松弛操作（V 为顶点数），确保所有可能的最短路径都被考虑到。

为什么需要 V-1 次迭代？

在无负权环的图中，最短路径最多包含 V-1 条边（否则路径会重复经过节点，形成环）。
通过 V-1 次松弛，可以确保所有最短路径被正确计算。

2. 算法步骤

初始化：
- 源点 src 的距离设为 0，其他节点的距离设为 ∞。
松弛所有边：
对图中的每条边 u → v，执行松弛操作。
重复此过程 V-1 次。
检测负权环：
再进行一次松弛操作，如果仍有边可被松弛，则说明图中存在负权环。

3. 时间复杂度

时间复杂度：
O(V·E)，其中 V 是顶点数，E 是边数。
由于需要松弛所有边 V-1 次，并额外检测负权环一次。
空间复杂度：
O(V)，存储每个节点的最短距离。

4. 优缺点

优点：

支持负权边：
可以正确处理包含负权边的图（前提是图中无负权环）。
检测负权环：
算法结束时可以判断图中是否存在从源点可达的负权环。
灵活性：
适用于各种图结构（有向图、无向图，但无向图的负权边等价于负权环）。

缺点：

时间复杂度高：
对于稠密图（E ≈ V²），时间复杂度为 O(V³)，远高于 Dijkstra 算法。
不适用大规模图：
当 V 和 E 较大时（如 V > 1000），效率显著下降。

图示：

代码实现

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-30 15:36:26
 * 最后修改: 2025-01-30 16:57:58
 * 文件描述: bellmanFord算法
****************************************************************/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 定义边的结构体
struct Edge {
    int src, dest, weight;
};

// Bellman-Ford算法函数
void bellmanFord(Edge edges[], int V, int E, int src) {
    vector<int> dist(V, INT_MAX); // 初始化距离数组，所有顶点的距离为无穷大
    dist[src] = 0; // 源顶点的距离为0
    bool flag = true; // 标志变量，用于检测负权重环

    // 进行V-1次松弛操作
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int weight = edges[j].weight;
            // 如果从u到v的距离可以缩短，则更新距离
            if(dist[u] != INT_MAX && dist[u] + weight < dist[v]) { 
                // 如果在第V次松弛操作中仍然可以更新距离，说明存在负权重环
                if(i == V - 1) {
                    cout << "Graph contains negative weight cycle" << endl;
                    flag = false;
                    break;
                }  
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 如果不存在负权重环，输出各顶点的最短距离
    if(flag) {
        cout << "Vertex Distance from Source" << endl;
        for(int i = 0; i < V; i++) {
            cout << i << "\t\t" << dist[i] << endl;
        }
    }
}

int main() {
    int V = 5; // 顶点数
    int E = 8; // 边数
    Edge edges[] = {
        {0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2},
        {3, 2, 5}, {3, 1, 1}, {4, 3, -3}
    };

    bellmanFord(edges, V, E, 0); // 调用Bellman-Ford算法
    return 0;
}

负权环情况

// Edge edges[E] = {
    //     {0, 1, 4},   // 0→1，权重4
    //     {0, 2, 5},   // 0→2，权重5
    //     {1, 2, -2},  // 1→2，权重-2
    //     {1, 3, 6},   // 1→3，权重6
    //     {2, 3, 3},   // 2→3，权重3
    //     {2, 4, 7},   // 2→4，权重7
    //     {3, 4, -1},  // 3→4，权重-1
    //     {4, 1, -5}   // 4→1，权重-5（此边会形成负权环）
    // };

Previous Topic

Back to Lesson

Next Topic