【代码随想录训练营第42期 Day59打卡 - 图论Part9 - Bellman-Ford算法
目录
一、Bellman-Ford算法
定义
特性
伪代码实现
二、经典题目
题目：卡码网 94. 城市间货物运输 I
题目链接
题解： Bellman-Ford算法
三、小结
一、Bellman-Ford算法
定义
Bellman-Ford算法是一个迭代算法，它可以处理包含负权边的图，并能够检测负权重环。算法的基本思想是通过对所有边进行多次“松弛”操作来逐步逼近最短路径。
特性
Bellman - Ford算法可以处理带有负权边的图。
它能够检测图中的负权重环。
如果图中存在负权重环，则算法无法计算出最短路径，因为负权重环可以使路径长度无限减小。
算法的最坏情况时间复杂度为 O(VE)，其中 V 是顶点数，E 是边数。
伪代码实现
function Bellman-Ford(graph, source):
// graph 是一个包含边信息的列表，每条边是一个三元组 (u, v, w)，表示从节点 u 到节点 v 的权值为 w
// source 是源节点的索引
// 初始化距离数组，所有节点的距离设置为无穷大，除了源节点设置为 0
distance[] = [∞ for i in 0 to graph.numberOfVertices]
distance[source] = 0
// 松弛操作，进行 V-1 次，其中 V 是图中的节点数
for i in 1 to graph.numberOfVertices - 1:
for each edge (u, v, w) in graph.edges:
// 如果从源节点到 u 的距离已知且从 u 到 v 的距离可以更短
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
// 检测图中是否存在负权重环
for each edge (u, v, w) in graph.edges:
if distance[u] + w < distance[v]:
return "Graph contains a negative-weight cycle"
// 返回距离数组，包含从源节点到所有其他节点的最短路径长度
return distance
二、经典题目
题目：卡码网 94. 城市间货物运输 I
题目链接
94. 城市间货物运输 I (kamacoder.com)
题目描述
某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。
网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。
城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。
输入描述
第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。
接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。
输出描述
如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。
输入示例
6 7 5 6 -2 1 2 1 5 3 1 2 5 2 2 4 -3 4 6 4 1 3 5输出示例
1提示信息
示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。
示例 2：
4 2
1 2 -1
3 4 -1在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 "unconnected"。
数据范围：
1 <= n <= 1000；
1 <= m <= 10000;-100 <= v <= 100;
题解： Bellman-Ford算法
关键在于松弛操作：
松弛操作：
这是算法的核心。对于图中的每一条边，如果可以通过这条边使得到达某个顶点的距离更短，则更新这个顶点的最短距离。这个过程会重复进行，直到无法再通过任何边来进一步缩短任何顶点的最短距离。
具体步骤：对于每一条边(u, v)，如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)。这里 dist[u] 是起点到顶点 u 的当前最短距离，weight(u, v) 是边(u, v) 的权重。
代码实现：
// Bellman-Ford算法
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<int>> grid; // 存储边
for (int i = 0; i < m; i++) // 将所有边保存起来
{
cin >> p1 >> p2 >> val;
grid.push_back({p1, p2, val}); // p1 指向 p2，权值为 val
}
int start = 1; // 起点
int end = n; // 终点
vector<int> minDist(n + 1, INT_MAX); // 初始化最短路径数组，所有节点的最短距离设置为INT_MAX，表示无穷大
minDist[start] = 0;
// Bellman-Ford算法的关键：对所有边进行n-1次松弛操作
for (int i = 1; i < n; i++)
{
for (vector<int> &side : grid) // 每一次松弛，都是对所有边进行松弛
{
int from = side[0]; // 边的出发点
int to = side[1]; // 边的到达点
int price = side[2]; // 边的权值
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price)
{
minDist[to] = minDist[from] + price;
}
}
}
if (minDist[end] == INT_MAX) // 不能到达终点
cout << "unconnected" << endl;
else
cout << minDist[end] << endl; // 到达终点最短路径
}三、小结
Bellman-Ford算法是解决某些特定类型的最短路径问题的有力工具，特别是当图中包含负权边时。但是其在众多最短路径算法中效率并不高，我们需要知道什么时候适合使用它。