【算法刷题】—7.25 Dijkstra 算法应用

简介: ✨今日算法一题网络延迟时间

✨今日算法一题


网络延迟时间


文章目录


网络延迟时间


题目描述

思路详解


本题运用Dijkstra 算法。

根据题意,从节点 k 发出的信号,到达节点 x 的时间就是节点 k 到节点 x 的最短路的长度。因此我们需要求出节点 k 到其余所有点的最短路,其中的最大值就是答案。若存在从 k 出发无法到达的点,则返回 −1。


代码与结果

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE / 2;
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], INF);
        }
        for (int[] t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[k - 1] = 0;
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; ++i) {
            int x = -1;
            for (int y = 0; y < n; ++y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true;
            for (int y = 0; y < n; ++y) {
                dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
            }
        }
        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;
    }
}


✨总结


今天主要复习了Dijkstra 算法,这也是很重要的一个算法,也要注意练习哦!


目录
打赏
0
0
0
0
0
分享
相关文章
MapReduce在实现PageRank算法中的应用
总结来说,在实现PageRank算法时使用MapReduce能够有效地进行大规模并行计算,并且具有良好的容错性和可扩展性。
182 76
公司局域网管理视域下 Node.js 图算法的深度应用研究:拓扑结构建模与流量优化策略探析
本文探讨了图论算法在公司局域网管理中的应用,针对设备互联复杂、流量调度低效及安全监控困难等问题,提出基于图论的解决方案。通过节点与边建模局域网拓扑结构,利用DFS/BFS实现设备快速发现,Dijkstra算法优化流量路径,社区检测算法识别安全风险。结合WorkWin软件实例,展示了算法在设备管理、流量调度与安全监控中的价值,为智能化局域网管理提供了理论与实践指导。
89 3
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
62 5
论上网限制软件中 Python 动态衰减权重算法于行为管控领域的创新性应用
在网络安全与行为管理的学术语境中,上网限制软件面临着精准识别并管控用户不合规网络请求的复杂任务。传统的基于静态规则库或固定阈值的策略,在实践中暴露出较高的误判率与较差的动态适应性。本研究引入一种基于 “动态衰减权重算法” 的优化策略,融合时间序列分析与权重衰减机制,旨在显著提升上网限制软件的实时决策效能。
72 2
公司员工电脑监控软件剖析:PHP 布隆过滤器算法的应用与效能探究
在数字化办公的浪潮下,公司员工电脑监控软件成为企业管理的重要工具,它能够帮助企业了解员工的工作状态、保障数据安全以及提升工作效率。然而,随着监控数据量的不断增长,如何高效地处理和查询这些数据成为了关键问题。布隆过滤器(Bloom Filter)作为一种高效的概率型数据结构,在公司员工电脑监控软件中展现出独特的优势,本文将深入探讨 PHP 语言实现的布隆过滤器算法在该软件中的应用。
73 1
基于 PHP 语言的滑动窗口频率统计算法在公司局域网监控电脑日志分析中的应用研究
在当代企业网络架构中,公司局域网监控电脑系统需实时处理海量终端设备产生的连接日志。每台设备平均每分钟生成 3 至 5 条网络请求记录,这对监控系统的数据处理能力提出了极高要求。传统关系型数据库在应对这种高频写入场景时,性能往往难以令人满意。故而,引入特定的内存数据结构与优化算法成为必然选择。
98 3
机器人路径规划和避障算法matlab仿真,分别对比贪婪搜索,最安全距离,RPM以及RRT四种算法
本程序基于MATLAB 2022A实现机器人路径规划与避障仿真,对比贪婪搜索、最安全距离、RPM和RRT四种算法。通过地图模拟环境,输出各算法的路径规划结果,展示其在避障性能与路径优化方面的差异。代码包含核心路径搜索逻辑,并附有测试运行图示,适用于机器人路径规划研究与教学演示。
110 64
基于精英个体保留策略遗传优化的生产调度算法matlab仿真
本程序基于精英个体保留策略的遗传算法,实现生产调度优化。通过MATLAB仿真,输出收敛曲线与甘特图,直观展示调度结果与迭代过程。适用于复杂多约束生产环境,提升资源利用率与调度效率。
基于FPGA的图像退化算法verilog实现,分别实现横向和纵向运动模糊,包括tb和MATLAB辅助验证
本项目基于FPGA实现图像运动模糊算法,包含横向与纵向模糊处理流程。使用Vivado 2019.2与MATLAB 2022A,通过一维卷积模拟点扩散函数,完成图像退化处理,并可在MATLAB中预览效果。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问