《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(49)万鸦壶焚网络 - 网络延迟时间(Bellman-Ford)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(49)万鸦壶焚网络 - 网络延迟时间(Bellman-Ford)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的万鸦壶网络,壶中网络错综复杂,节点之间的延迟各不相同。壶的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此壶,需以万鸦壶之力,焚网络,网络延迟显真身。”
哪吒定睛一看,石碑上还有一行小字:“网络拓扑结构如下,节点K
到其他所有节点的最短延迟时间的最大值即为网络延迟时间。”哪吒心中一动,他知道这是一道关于网络延迟时间的难题,需要通过Bellman-Ford算法来计算从起点到所有节点的最短路径,进而找到最大延迟时间。
暴力解法:万鸦壶的初次尝试
哪吒心想:“要计算网络延迟时间,我可以尝试所有可能的路径。”他催动万鸦壶之力,从起点节点开始,逐个节点访问,记录每条路径的延迟时间,试图找到最短路径。
#include <vector>
#include <climits>
using namespace std;
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
for (int i = 0; i < n - 1; ++i) {
for (auto& time : times) {
int u = time[0];
int v = time[1];
int w = time[2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
int maxDelay = 0;
for (int i = 1; i <= n; ++i) {
if (dist[i] == INT_MAX) return -1;
maxDelay = max(maxDelay, dist[i]);
}
return maxDelay;
}
哪吒成功地计算了网络延迟时间,但万鸦壶的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当网络节点数量很多时,灵力消耗巨大。
C++语法点
在C++中,Bellman-Ford算法涉及到图的邻接表表示和距离数组的更新。以下是一些重要特性:
-
邻接表:
- 使用
vector<vector<int>>
表示图的邻接表。 - 常用操作:
times
:存储所有边的信息,每条边包含起点、终点和权重。
- 使用
-
距离数组