当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的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:存储所有边的信息,每条边包含起点、终点和权重。
  • 距离数组


http://www.kler.cn/a/590488.html

相关文章:

  • Spring boot+mybatis的批量删除
  • 【AI】深度学习与人工智能应用案例详解
  • LIMS系统在纸制品制造的应用 内检实验室LIMS系统提升纸制品质控
  • Postman发送GET请求示例及注意事项
  • Vue.js 事件处理与修饰符详解
  • 2. qt写带有槽的登录界面(c++)
  • 玩转python:通俗易懂掌握高级数据结构-collections模块之UserDict
  • 人工智能之数学基础:从线性变换理解矩阵范数和矩阵行列式
  • 第一中标人!晶科能源入围大唐集团19.5GW光伏组件集采
  • 遥感新态势:Sentinel - 2多光谱指数与AI深度融合
  • 卡内基梅隆大学研究人员推出 PAPRIKA:一种微调方法,使语言模型能够发展出不局限于特定环境的通用决策能力
  • 基于javaweb的SpringBoot博客商城管理系统设计与实现(源码+文档+部署讲解)
  • 通过 Python 爬虫提高股票选股胜率
  • Linux快速安装mysql
  • 3D 射线方程学习
  • 青少年编程与数学 02-010 C++程序设计基础 43课题、MFC
  • 鸿蒙应用开发--数据埋点的名称由来,发展脉络,典型场景,现代演进的无埋点和智能化埋点//学习时长数据埋点的实现--待更新
  • DNS查询
  • Matlab 汽车传动系统的振动特性分析
  • LeetCode 解题思路 16(Hot 100)