1. 最短路径概述

在计算机科学和图论领域中，图的最短路径问题是一个非常重要且经典的问题。图是由顶点（节点）和连接这些顶点的边组成的数据结构，在许多实际场景中都有广泛应用，如地图导航、网络路由、社交网络分析等。最短路径问题的目标是在一个图中找到从一个特定的起始顶点到另一个目标顶点的路径，使得这条路径上所有边的权值之和最小。

依据图中边是否具有方向对最短路径进行分类，可将其明确划分为有向图最短路径和无向图最短路径这两类。

1.1 有向图的最短路径

在有向图中，边是有方向的，从顶点u到顶点v的路径必须沿着边的方向进行。因此，有向图中顶点之间的可达性和最短路径是有方向性的，即从u到v的最短路径和从v到u的最短路径可能不同，甚至一个方向可达而另一个方向不可达。

有向图的的最短路径的应用场景举例：

1. 交通网络：例如城市中的单行道网络，车辆只能按照规定的方向行驶，就可以用有向图来表示，计算从一个地点到另一个地点的最短路径。
2. 任务调度：在项目管理中，任务之间存在先后依赖关系，用有向边表示任务的先后顺序，可通过计算有向图的最短路径来确定项目的最短完成时间。

然后，我们再来了解一下有向图最短路径的求解方式：

1. 迪杰斯特拉（Dijkstra）算法：要求图中所有边的权值非负，通过贪心策略从源点开始逐步扩展，每次选择距离源点最近且未确定最短路径的顶点，以该顶点为中间点更新其他顶点到源点的距离。
2. 弗洛伊德（Floyd）算法：该算法用于求解图中所有顶点对之间的最短路径。其基本思想是通过动态规划的方法，依次考虑每个顶点作为中间顶点，更新任意两个顶点之间的最短距离。
3. 贝尔曼 - 福特（Bellman - Ford）算法：可以处理有向图中存在负权边的情况，但不能存在负权回路。

1.2 无向图的最短路径

无向图中的边没有方向，即如果存在一条边连接顶点u和v，那么从u到v和从v到u是等价的。所以无向图中任意两个顶点之间的最短路径是双向相同的。在无权图中，每条边的权值都被视为 1。此时，最短路径就是经过边的数量最少的路径。

无向图最短的应用场景举例：

1. 社交网络：社交网络中人与人之间的关系可以用无向图表示，计算两个人之间的最短社交关系链就是求无向图的最短路径。
2. 物理网络：如电力网络、水管网络等，这些网络中的连接通常是双向的，可使用无向图来建模并求解最短路径问题。

无向图的最短路径求解算法与有向图基本相同，因为无向图可以看作是每条无向边都对应两条方向相反、权值相同的有向边的有向图。可用的算法如下：

1. 迪杰斯特拉（Dijkstra）算法：同样适用于边权非负的无向图，求解过程和有向图一致。
2. 弗洛伊德（Floyd）算法：同样适用于无向图，求解过程和有向图一致。
3. 贝尔曼 - 福特（Bellman - Ford）算法：同样适用于无向图，前提是不存在负权回路。
4. 广度优先搜索（BFS）：当无向图的边权都为 1 时，使用广度优先搜索可以高效地找到最短路径。BFS 从源点开始，逐层扩展，当第一次到达目标顶点时，所经过的路径就是最短路径，时间复杂度为 O(V+E)。

接下来，我们使用邻接表的方式给大家讲解下无向图最短路径的搜索，例图如下：

根据这个图中节点之间的关系就可以使用STL容器构建出一个邻接表：

1
2
3
4
5
6
7
8
9

vector<vector<int>> graph = {
    {1, 2},
    {0, 2, 3},
    {0, 1, 3},
    {1, 2, 4, 5}, 
    {3, 5, 6}, 
    {3, 4, 6}, 
    {4, 5}  
};

现在要求找出顶点0到顶点4的最短路径，示例函数如下：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

// 使用 BFS 找到所有最短路径
vector<vector<int>> findShortPathBFS(const vector<vector<int>>& graph, int start, int end)
{
    int n = graph.size();
    vector<int> dist(n, numeric_limits<int>::max());
    vector<vector<int>> prev(n);
    vector<bool> visited(n, false);

    queue<int> q;
    q.push(start);
    dist[start] = 0;
    visited[start] = true;
    while (!q.empty()) 
    {
        int current = q.front();
        q.pop();
        for (int neighbor : graph[current]) 
        {
            if (!visited[neighbor]) 
            {
                dist[neighbor] = dist[current] + 1;
                prev[neighbor].push_back(current);
                visited[neighbor] = true;
                q.push(neighbor);
            }
            else if (dist[neighbor] == dist[current] + 1) 
            {
                prev[neighbor].push_back(current);
            }
        }
    }

    // 递归回溯所有最短路径
    vector<vector<int>> allPaths;
    vector<int> path;
    function<void(int)> backtrack = [&](int at) {
        path.push_back(at);
        if (at == start) 
        {
            vector<int> reversedPath = path;
            reverse(reversedPath.begin(), reversedPath.end());
            allPaths.push_back(reversedPath);
        }
        else 
        {
            for (int p : prev[at]) 
            {
                backtrack(p);
            }
        }
        path.pop_back();
    };
    backtrack(end);

    return allPaths;
}

void shortPathBFSTest()
{
    vector<vector<int>> graph = {
        {1, 2},
        {0, 2, 3},
        {0, 1, 3},
        {1, 2, 4, 5}, 
        {3, 5, 6}, 
        {3, 4, 6}, 
        {4, 5} 
    };

    int start = 0;
    int end = 4;
    vector<vector<int>> paths = findShortPathBFS(graph, start, end);
    if (paths.empty())
    {
        cout << "No path found from " << start << " to " << end << endl;
    }
    else
    {
        cout << "All shortest paths from " << start << " to " << end << ":\n";
        for (const auto& path : paths)
        {
            for (int node : path)
            {
                cout << node << " ";
            }
            cout << endl;
        }
    }
}

int main() 
{
    shortPathBFSTest();
    return 0;
}

程序输出的结果为：

1
2
3

All shortest paths from 0 to 4:
0 1 3 4
0 2 3 4

关于上述代码的相关细节说明:

1. 初始化
   • dist：记录每个节点到起点的最短距离，初始化为无穷大。
   • prev：记录每个节点的前驱节点，用于回溯路径。
   • visited：标记节点是否已经被访问过。
2. BFS 遍历核心逻辑
   • 使用队列 q 进行 BFS 遍历。
   • 将起点 start 入队，设置其距离为 0，并标记为已访问。
   • 从队列中取出当前节点 current。
   • 如果 current 是终点 end，停止搜索。
   • 遍历current的所有邻接节点neighbor：
     • 如果 neighbor 未被访问过，更新其距离、前驱节点，并标记为已访问。
     • 如果 neighbor 已被访问过，但当前路径也是最短路径，更新其前驱节点。
3. 路径回溯
   • 使用 function<void(int)> 定义一个递归函数 backtrack，参数为当前节点 at。
   • 将当前节点 at 添加到路径 path 中。
   • 如果当前节点 at 是起点 start，说明找到了一条完整路径。
     • 将路径 path 反转（因为路径是从终点回溯到起点的），并存储到 allPaths 中。
   • 如果当前节点 at 不是起点，继续回溯。
     • 遍历当前节点 at 的所有前驱节点 p，递归调用 backtrack(p)。
   • 在递归返回时，通过path.pop_back()将当前节点 at 从路径 path 中移除，以便尝试其他路径。

2. 迪杰斯特拉算法

迪杰斯特拉（Dijkstra）算法是一种用于求解带权有向图或无向图中单个源节点到其他所有节点的最短路径的贪心算法。该算法要求图中所有边的权值非负。该算法的基本思想是：从源节点开始，逐步扩展到距离源节点最近的节点，并更新这些节点到源节点的最短距离。具体步骤如下：

1. 初始化：将源节点的距离设为 0，其他节点的距离设为无穷大。同时，创建一个集合来记录已经确定最短路径的节点。
2. 选择节点：从未确定最短路径的节点中选择距离源节点最近的节点，将其加入已确定最短路径的集合。
3. 更新距离：对于新加入集合的节点的所有邻接节点，检查通过该节点到达邻接节点的距离是否比当前记录的距离更短。如果是，则更新邻接节点的距离。
4. 重复步骤 2 和 3：直到所有节点都被加入已确定最短路径的集合。

下面以一个简单的带权有向图为例，来详细展示迪杰斯特拉算法的执行过程。假设有一个包含 5 个节点（编号为 0 - 4）的带权有向图，其邻接矩阵表示如下（我们选择节点 A 作为源节点）：

这里 INF 表示两个节点之间没有直接相连的边（权值无穷大）。

算法执行过程如下：

1. 初始化

   • 距离数组dist存储每个节点到源节点的最短距离，初始时，源节点A的距离设为0，其他节点的距离设为无穷大。
     • dist = [0, INF, INF, INF, INF]
   • 创建一个集合visited来记录已经确定最短路径的节点，初始时为空。
     • visited = { }

2. 选择节点

   从未确定最短路径的节点中选择距离源节点最近的节点，当前只有节点A的距离已知且为0，将节点A加入visited集合。即：visited = { A }

3. 更新距离

   节点A的邻接节点有B和C，边的权值分别为 4 和 2。

   • 对于节点B(1)：通过节点A到达节点B的距离为4，小于当前记录的无穷大，更新 dist[1] 为 4。
   • 对于节点C(2)：通过节点A到达节点C的距离为2，小于当前记录的无穷大，更新 dist[2] 为 2。
   • 更新后的 dist = [0, 4, 2, INF, INF]

接下来继续重复上面的步骤 2 和 3。

• 第二次迭代

  • 选择节点：从未确定最短路径的节点（B, C, D, E）中选择距离源节点最近的节点，即节点 C（距离为 2），将节点C加入visited集合。

    • visited = { A, C }

  • 更新距离：节点C的邻接节点有B和D，边的权值分别为1和3。

    • 对于节点B：通过节点C到达节点B的距离为 dist[2] + 1 = 2 + 1 = 3，小于当前记录的 4，更新 dist[1] 为 3。
    • 对于节点D：通过节点C到达节点D的距离为 dist[2] + 3 = 2 + 3 = 5，小于当前记录的无穷大，更新 dist[3] 为 5。
    • 更新后的 dist = [0, 3, 2, 5, INF]

• 第三次迭代

  • 选择节点：从未确定最短路径的节点（B, D, E）中选择距离源节点最近的节点，即节点B（距离为 3），将节点B加入visited集合。

    • visited = { A, C, B }

  • 更新距离：节点B的邻接节点有C和D，边的权值分别为5和10。

    • 对于节点C：通过节点B到达节点C的距离为 dist[1] + 5 = 3 + 5 = 8，大于当前记录的 2，不更新 dist[2]。
    • 对于节点D：通过节点B到达节点D的距离为 dist[1] + 10 = 3 + 10 = 13，大于当前记录的 5，不更新 dist[3]。
    • dist = [0, 3, 2, 5, INF]

• 第四次迭代

  • 选择节点：从未确定最短路径的节点（D, E）中选择距离源节点最近的节点，即节点D（距离为 5），将节点D加入visited集合。

    • visited = { A, C, B, D }

  • 更新距离：节点D的邻接节点有E，边的权值为 7。

    • 对于节点E：通过节点D到达节点E的距离为 dist[3] + 7 = 5 + 7 = 12，小于当前记录的无穷大，更新 dist[4] 为 12。
    • 更新后的 dist = [0, 3, 2, 5, 12]

• 第五次迭代

  • 选择节点：未确定最短路径的节点只剩下E，将节点E加入visited 集合。

    • visited = { A, C, B, D, E }

  • 更新距离：节点E没有邻接节点，不进行更新。

    • dist = [0, 3, 2, 5, 12]

经过上述迭代，所有节点都被加入 visited 集合，dist 数组存储了每个节点到源节点A的最短距离：

• 节点A到节点A的最短距离为 0。
• 节点A到节点B的最短距离为 3。
• 节点A到节点C的最短距离为 2。
• 节点A到节点D的最短距离为 5。
• 节点A到节点E的最短距离为 12。

迪杰斯特拉算法的 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

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start)
{
    int n = graph.size();
    vector<int> dist(n, numeric_limits<int>::max());
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) 
    {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (const auto& edge : graph[u]) 
        {
            int v = edge.first;
            int weight = edge.second;
            if (!visited[v] && dist[u] + weight < dist[v]) 
            {
                dist[v] = dist[u] + weight;
                pq.push({ dist[v], v });
            }
        }
    }
    return dist;
}

void dijkstraTest()
{
    // 示例图的邻接表表示
    vector<vector<pair<int, int>>> graph = {
        {{1, 4}, {2, 2}},
        {{2, 5}, {3, 10}},
        {{1, 1}, {3, 3}},
        {{4, 7}},
        {}
    };

    int start = 0;
    vector<int> dist = dijkstra(graph, start);
    for (int i = 0; i < dist.size(); ++i) 
    {
        cout << "从节点 " << start << " 到节点 " << i << " 的最短路径是: ";
        if (dist[i] == numeric_limits<int>::max()) 
        {
            cout << "INF" << endl;
        }
        else 
        {
            cout << dist[i] << endl;
        }
    }
}

int main() 
{
    dijkstraTest();
    return 0;
}

终端打印的结果如下:

1
2
3
4
5

从节点 0 到节点 0 的最短路径是: 0
从节点 0 到节点 1 的最短路径是: 3
从节点 0 到节点 2 的最短路径是: 2
从节点 0 到节点 3 的最短路径是: 5
从节点 0 到节点 4 的最短路径是: 12

关于示例函数中的细节描述如下:

1. 函数参数与返回值

   • 返回值：返回一个 std::vector<int> 类型的数组

     在测试程序中 dist[i] 表示从起始节点 start 到节点 i 的最短路径长度。

   • 参数：

     • graph：一个二维的 std::vector，用于表示图的邻接表。graph[i] 存储了节点 i 的所有邻接节点及其对应的边的权重，每个邻接节点和边的权重用 std::pair<int, int> 表示，其中第一个元素是邻接节点的编号，第二个元素是边的权重。
     • start：起始节点的编号。

2. 优先队列

   优先队列（std::priority_queue）是 C++ 标准库中的一种容器适配器，它类似于普通的队列，但元素的出队顺序不是按照入队顺序，而是按照元素的优先级。默认情况下，优先队列是一个最大堆，即优先级最高的元素（数值最大的元素）总是位于队列的顶部。不过，通过指定不同的比较函数，我们可以将其转换为最小堆，使得优先级最低的元素（数值最小的元素）位于队列顶部。

   1	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

   • pair<int, int>

     这是优先队列中存储的元素类型。在 Dijkstra 算法的上下文中，每个 std::pair<int, int> 表示一个节点及其当前的最短路径长度。具体来说，第一个 int 表示从起始节点到该节点的最短路径长度，第二个 int 表示节点的编号。例如，{5, 3} 表示节点 3 的当前最短路径长度为 5。

   2. vector<pair<int, int>>

      这是优先队列所使用的底层容器类型。优先队列本身是一个容器适配器，它需要一个底层容器来实际存储元素。

   3. greater<pair<int, int>>

      这是一个比较函数对象，用于定义优先队列中元素的优先级顺序。通过 std::greater 比较函数，优先队列实现了最小堆的行为，确保每次取出距离最小的节点，从而保证算法的正确性和效率。

3. 时间复杂度

   算法需要进行V(顶点数量)次迭代，每次迭代从优先队列中取出距离源节点最近的节点，时间复杂度为 O(log⁡V)；然后更新该节点的所有邻接节点的距离，由于使用邻接表存储图，检查每个节点的邻接节点需要 O(E)的时间，其中E是图中边的数量。对于每条边，更新其邻接节点的距离并调整优先队列的时间复杂度为O(log⁡V)。因此，核心循环的总时间复杂度为O((V+E)log⁡V)。

3. 弗洛伊德算法

弗洛伊德算法（Floyd-Warshall）是一种用于计算图中所有节点之间最短路径的动态规划算法。它能够处理有向图和无向图，同时可以检测负权边，但无法处理包含负权环的图。该算法的时间复杂度为 O(n³)，其中n是图中节点的数量。尽管时间复杂度较高，但它在节点数量较小的图中是一个简单且有效的解决方案。

负权环就是说，在这个环中，所有边的权重加起来是负数。比如，假设A到B的边权重是 -1，B到C的边权重是 -3，C到A的边权重是 2。那么，整个环的权重总和是 2 + (-3) + (-1) = -2，这是一个负权环。

弗洛伊德算法通过逐步考虑每个节点作为中间节点，来更新所有节点对之间的最短路径。具体步骤如下：

1. 初始化距离矩阵：创建一个二维数组dist，其中dist[i][j]表示节点i到节点j的初始距离。如果节点i和节点j之间没有直接边，则初始距离设为无穷大（表示不可达）。
2. 逐步更新最短路径：对于每个中间节点k（从1到n），遍历所有节点对(i, j)，检查是否可以通过节点k作为中间节点来缩短i到j的路径。即，比较dist[i][j]和dist[i][k] + dist[k][j]，选择较小的一个作为新的dist[i][j]。
3. 处理负权边：如果图中存在负权边，算法仍然可以正确计算最短路径，但需要确保图中没有负权环，否则最短路径将不存在。
4. 输出结果：经过所有中间节点的处理后，dist矩阵中的值即为所有节点对之间的最短路径。

比如要计算顶点A到顶点D的距离，初始状态下dist[a][d] = INF:

• 比较dist[a][d] = INF和dist[a][b] + dist[b][d] = 14，选择较小值更新dist[a][d] = 14
• 比较dist[a][d] = 14和dist[a][c] + dist[c][d] = 5，选择较小值更新dist[a][d] = 5
• 找到顶点A到顶点D的最短路径为5

可以看到，弗洛伊德算法在逻辑上是非常简单的，以下是该算法的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

vector<vector<int>> floydWarshall(vector<vector<int>>& graph)
{
    int n = graph.size();
    const int INF = numeric_limits<int>::max();
    vector<vector<int>> dist = graph;

    for (int k = 0; k < n; ++k) 
    {
        for (int i = 0; i < n; ++i) 
        {
            for (int j = 0; j < n; ++j) 
            {
                if (dist[i][k] != INF && dist[k][j] != INF) 
                {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) 
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) 
    {
        if (dist[i][i] < 0) 
        {
            cout << "图中存在负权环，无法计算最短路径。" << endl;
            return vector<vector<int>>();
        }
    }
    return dist;
}

void floydWarshallTest()
{
    const int INF = numeric_limits<int>::max();
    vector<vector<int>> graph = {
        {0, 4, 2, INF, INF},
        {INF, 0, 5, 10, INF},
        {INF, 1, 0, 3, INF},
        {INF, INF, INF, 0, 7},
        {INF, INF, INF, INF, 0}
    };
    auto dist = floydWarshall(graph);
    for (int i = 0; i < dist.size(); ++i)
    {
        for (int j = 0; j < dist.size(); ++j)
        {
            if (dist[i][j] == INF)
            {
                cout << "从节点 " << i << " 到节点 " << j << " 没有路径。" << endl;
            }
            else
            {
                cout << "从节点 " << i << " 到节点 " << j << " 的最短距离是: " << dist[i][j] << endl;
            }
        }
    }
}

int main() 
{
    floydWarshallTest();
    return 0;
}

程序终端输出的结果为：

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

从节点 0 到节点 0 的最短距离是: 0
从节点 0 到节点 1 的最短距离是: 3
从节点 0 到节点 2 的最短距离是: 2
从节点 0 到节点 3 的最短距离是: 5
从节点 0 到节点 4 的最短距离是: 12
从节点 1 到节点 0 没有路径。
从节点 1 到节点 1 的最短距离是: 0
从节点 1 到节点 2 的最短距离是: 5
从节点 1 到节点 3 的最短距离是: 8
从节点 1 到节点 4 的最短距离是: 15
从节点 2 到节点 0 没有路径。
从节点 2 到节点 1 的最短距离是: 1
从节点 2 到节点 2 的最短距离是: 0
从节点 2 到节点 3 的最短距离是: 3
从节点 2 到节点 4 的最短距离是: 10
从节点 3 到节点 0 没有路径。
从节点 3 到节点 1 没有路径。
从节点 3 到节点 2 没有路径。
从节点 3 到节点 3 的最短距离是: 0
从节点 3 到节点 4 的最短距离是: 7
从节点 4 到节点 0 没有路径。
从节点 4 到节点 1 没有路径。
从节点 4 到节点 2 没有路径。
从节点 4 到节点 3 没有路径。
从节点 4 到节点 4 的最短距离是: 0

1. 常量 INF：表示无穷大，用于初始化没有直接连接的节点对之间的距离。
   • 在C++中，虽然也可以使用INT_MAX，但更推荐使用std::numeric_limits<int>::max()，因为它更符合C++的风格，并且提供了更好的类型安全性和可扩展性。
   • std::numeric_limits<int>::max()返回的是int类型能够表示的最大值。在大多数系统中，int是32位的有符号整数，所以它的最大值应该是 2³¹ -1，也就是 2147483647。
2. floydWarshall 函数：
   • 首先将 dist 矩阵初始化为输入图的邻接矩阵 graph。
   • 通过三重循环，尝试以每个节点 k 作为中间节点，更新所有节点对 (i, j) 之间的最短距离。
   • 循环结束后，检查是否存在负权环（即是否有 dist[i][i] < 0），如果存在则输出提示信息并返回。
   • 最后输出所有节点对之间的最短距离。
3. floydWarshallTest 函数：
   • 定义一个示例图的邻接矩阵 graph。
   • 调用 floydWarshall 函数来计算并输出所有节点对之间的最短距离。

4. 贝尔曼 - 福特算法

贝尔曼 - 福特（Bellman - Ford）算法是一种用于求解单源最短路径问题的算法，它和迪杰斯特拉算法类似，但不同的是，贝尔曼 - 福特算法可以处理图中存在负权边的情况，不过如果图中存在负权环，它可以检测出来。

贝尔曼 - 福特算法的核心思想是对图中的所有边进行 V - 1 次松弛操作（V 是图中顶点的数量），每次松弛操作都会尝试更新从源点到各个顶点的最短距离。在进行 V - 1 次松弛操作后，如果图中不存在负权环，那么此时得到的最短距离就是最终结果；如果还能继续更新最短距离，就说明图中存在负权环。

假设我们有一个图G=(V,E)，其中V是顶点的集合，E是边的集合。对于每条边 (u,v)∈E，有一个权重 w(u,v)表示从顶点u到顶点v的距离。我们还维护一个距离数组dist，其中dist[v]表示从源点 s到顶点 v的当前最短距离估计值。

松弛操作就是针对某条边(u,v)进行检查，如果通过顶点u到达顶点v的距离比当前记录的dist[v]更短，就更新dist[v]的值。以下是对边(u,v)进行松弛操作的具体步骤：

1. 检查从源点到顶点u是否可达：首先要确保从源点到顶点u是有路径的，即dist[u]不能是无穷大（在代码实现中通常用一个很大的数，如 INT_MAX 表示）。
2. 计算通过顶点u到达顶点v的距离：如果从源点到顶点u可达，计算从源点经过顶点u再到顶点v的距离，即dist[u] + w(u,v)。
3. 比较距离并更新：将计算得到的距离dist[u] + w(u,v)与当前记录的dist[v]进行比较。如果 dist[u] + w(u,v) < dist[v]，说明通过顶点u到达顶点v的路径更短，就更新dist[v]的值为 dist[u] + w(u,v)。

假设有一个简单的图，包含三个顶点 A、B、C，边(A,B)的权重为-1，边(B,C)的权重为3，边(A,C)的权重为4。源点为A。

• 初始时，dist[A]=0，dist[B]=∞，dist[C]=∞。
• 对边 (A,B)进行松弛操作：因为 dist[A]=0且0+(-1)<∞，所以更新dist[B]=-1。
• 对边 (B,C)进行松弛操作：因为dist[B]=-1且-1+3<∞，所以更新dist[C]=2。
• 对边 (A,C)进行松弛操作：因为 dist[A]=0且0+4>2，所以dist[C]保持不变。

最终得到从源点A到顶点B的最短距离为-1，到顶点C的最短距离为2。

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
71
72
73
74
75
76
77
78
79
80
81
82
83

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

// 定义图的结构体
struct Graph 
{
    int V, E;  // V 是顶点数，E 是边数
    vector<Edge> edges;
};

vector<int> bellmanFord(Graph graph, int src)
{
    int V = graph.V;
    int E = graph.E;
    vector<int> dist(V, INT_MAX); 
    dist[src] = 0; 

    for (int i = 1; i <= V - 1; i++) 
    {
        for (int j = 0; j < E; j++) 
        {
            int u = graph.edges[j].src;
            int v = graph.edges[j].dest;
            int weight = graph.edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
            {
                dist[v] = dist[u] + weight;
            }
        }
    }

    for (int i = 0; i < E; i++) 
    {
        int u = graph.edges[i].src;
        int v = graph.edges[i].dest;
        int weight = graph.edges[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) 
        {
            cout << "图中存在负权环，无法计算最短路径。" << endl;
            return vector<int>();
        }
    }
    return dist;
}

void bellmanFordTest()
{
    Graph graph;
    graph.V = 5;  // 5 个顶点
    graph.E = 8;  // 8 条边

    // 添加边
    graph.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}
    };

    int src = 0;  
    auto dist = bellmanFord(graph, src);
    cout << "从源点 " << src << " 到各个顶点的最短距离为：" << endl;
    for (int i = 0; i < dist.size(); i++)
    {
        if (dist[i] == INT_MAX)
        {
            cout << "顶点 " << i << ": 无法到达" << endl;
        }
        else
        {
            cout << "顶点 " << i << ": " << dist[i] << endl;
        }
    }
}

int main() 
{
    bellmanFordTest();
    return 0;
}

终端打印的结果如下:

1
2
3
4
5
6

从源点 0 到各个顶点的最短距离为：
顶点 0: 0
顶点 1: -1
顶点 2: 2
顶点 3: -2
顶点 4: 1

1. 结构体定义：
   • Edge 结构体：用于表示图中的边，包含三个成员变量 src（边的起点）、dest（边的终点）和 weight（边的权重）。
   • Graph 结构体：用于表示图，包含两个成员变量 V（图中顶点的数量）、E（图中边的数量）以及一个存储边的向量 edges。
2. bellmanFord 函数：
   • 初始化：创建一个长度为 V 的距离数组 dist，并将所有元素初始化为 INT_MAX（表示无穷大），将源点的距离初始化为 0。
   • 松弛操作：进行 V - 1 次松弛操作，每次遍历所有的边。对于每条边 (u, v)，如果从源点到 u 有路径，并且通过 u 到 v 的路径更短，则更新 dist[v] 的值。
   • 负权环检测：在进行 V - 1 次松弛操作后，再遍历一次所有的边。如果还能更新 dist 数组中的值，说明图中存在负权环，输出提示信息并返回 false。
   • 输出结果：如果图中不存在负权环，输出从源点到各个顶点的最短距离。
3. INT_MAX 是 C 和 C++ 标准库中定义的一个常量
   • 在 C 语言里，INT_MAX 定义于 <limits.h> 头文件；而在 C++ 中，它同样可以通过包含 <climits>（C++ 标准库中对应 C 语言 <limits.h> 的头文件）来使用。
   • INT_MAX 代表了 int 类型所能表示的最大数值。在绝大多数系统中，int 类型是 32 位的，采用补码形式来表示整数。对于 32 位有符号整数，其取值范围是 -2147483648（即 -2^31）到 2147483647（即 2^31 - 1），所以 INT_MAX 的值通常就是 2147483647。
4. 时间复杂度
   • 稀疏图：在稀疏图中，边的数量E通常远小于 V²，此时 O(V×E)的复杂度相对较低。
   • 稠密图：在稠密图中，边的数量E接近 V²，此时Bellman - Ford算法的时间复杂度接近O(V³)。