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

《庆余年算法番外篇》:范闲通过最短路径算法在阻止黑骑截杀林相

剧情背景

在《庆余年 2》22集中,林相跟大宝交代完为人处世的人生哲理之后,就要跟大宝告别了
在这里插入图片描述

在《庆余年 2》23集中,林相在告老还乡的路上与婉儿和大宝告别后在这里插入图片描述
范闲也在与婉儿的对话中知道黑骑调动是绝密,并把最近一次告老还乡梅执礼被马匪截杀与黑骑调动日期关联在一起,范闲知道了老皇帝要杀林相消息,所以范闲必须尽快找到一条最短路径在黑骑到之前去营救林相。这时候范闲在另外一个世界带来的记忆突然奔袭而来,马上想到用于地图导航GPS的Dijkstra算法,得找到路程最短的路径赶在黑骑到达前才能拯救林相,而在此之前他早就把庆国地形和路径都让人探究清楚了。知道黑骑所在位置到林相的位置大概需要75分钟。

现状输入描述

  • 起点A:范闲目前所在的位置。
  • 中点B:林相目前所在的位置。
  • 节点集:A和B之间的多个节点路口CDEGF(例如路上的交叉点、村庄等)。
  • 路程:连接这些节点的道路,每条道路有对应的行驶时间。

在这里插入图片描述

使用Dijkstra算法求解最短路径

实现原理

  1. Dijkstra 算法从指定的节点(源节点)出发,寻找它与图中所有其它节点之间的最短路径。
  2. Dijkstra 算法会记录当前已知的最短路径,并在寻找到更短的路径时更新。
  3. 一旦找到源节点与其他节点之间的最短路径,那个节点会被标记为“已访问”并添加到路径中。
  4. 重复寻找过程,直到图中所有节点都已经添加到路径中。这样,就可以得到从源节点出发访问所有其他节点的最短路径方案。

以下是详细的步骤和计算过程:

步骤 1: 初始化

  • 起点A到所有其他节点的初始距离设为无穷大,除了起点本身,其距离为0。
  • 使用优先队列初始化,从起点A开始。
距离:
A: 0
C: ∞
D: ∞
E: ∞
F: ∞
G: ∞
B: ∞优先队列:
[(0, 'A')]

步骤 2: 处理节点A

  • 从A出发,可以到C和D,更新距离。
    在这里插入图片描述

步骤 3: 处理节点C

  • 从C出发,可以到E,更新距离。
    在这里插入图片描述

步骤 4: 处理节点D

  • 从D出发,可以到E,但已有更短路径 C -> E,不更新。
距离:
A: 0
C: 15
D: 20
E: 25
F: ∞
G: ∞
B: ∞优先队列:
[(25, 'E')]

步骤 5: 处理节点E

  • 从E出发,可以到F和G,更新距离。
    在这里插入图片描述

步骤 6: 处理节点F

  • 从F出发,可以到B,更新距离。
距离:
A: 0
C: 15
D: 20
E: 25
F: 43
G: 45
B: 88优先队列:
[(45, 'G'), (88, 'B')]

步骤 7: 处理节点G

  • 从G出发,可以到B,更新距离。
    在这里插入图片描述

结果

通过Dijkstra算法计算,范闲从A到B的最短路径是A -> C -> E -> G -> B,总时间为:

  • A -> C:15分钟
  • C -> E:10分钟
  • E -> G:20分钟
  • G -> B:25分钟
  • 总时间:15 + 10 + 20 + 25 = 70分钟 (黑骑到林相需要75分钟)
    这时候选择A -> C -> E -> G -> B 因为没有导航刚刚手动计算已经花了两分钟了,情况紧急叫来王启年,马上赶路
    王启年说范闲我们两个打不过黑骑,但是范闲说情况紧急没法给你找兵马,要去拼一把,跟打工人不给资源不给权利但是还要让你做出业绩一样、跟研究生不给钱不给署名还要写出论文一样
    在这里插入图片描述
    这里可以看出王启年作为一个优秀员工,肯定每年拿E,这表情比老板还急
    在这里插入图片描述

从这里可以看出来,王启年业务能力也是一流,跑的比骑马快
在这里插入图片描述
按预期时间总算到了,开始正面刚黑骑
在这里插入图片描述
王启年虽然辛苦,但是范闲作为老板还是能抗事,马上承担责任,确保拿到结果,取得业绩有超强的领导力,是一个好老板
在这里插入图片描述

参考代码

import heapqdef dijkstra(graph, start):queue = [(0, start)]distances = {node: float('inf') for node in graph}distances[start] = 0while queue:current_distance, current_node = heapq.heappop(queue)if current_distance > distances[current_node]:continuefor neighbor, weight in graph[current_node].items():distance = current_distance + weightif distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(queue, (distance, neighbor))return distances# 图的邻接表表示
graph = {'A': {'C': 15, 'D': 20},'C': {'A': 15, 'E': 10},'D': {'A': 20, 'E': 15},'E': {'C': 10, 'D': 15, 'F': 18, 'G': 20},'F': {'E': 18, 'B': 45},'G': {'E': 20, 'B': 25},'B': {'F': 45, 'G': 25}
}# 计算从起点A到各节点的最短路径
start = 'A'
distances = dijkstra(graph, start)
print(f"从{start}到各节点的最短路径: {distances}")

写到最后

希望文章能让大家放松的同时有知识进入到脑子里
这里作者祝大家:

  • 高考\期末考的同学们:笔尖跃动光辉梦,心中理想定成真
  • 毕业生们:才华扬帆乘风起,壮志凌云展未来
  • 正在工作:不畏艰难勇向前,努力奋斗创佳绩
  • 老板领导们:睿智领导拓新路,胸怀广阔业绩殊

相关文章:

《庆余年算法番外篇》:范闲通过最短路径算法在阻止黑骑截杀林相

剧情背景 在《庆余年 2》22集中&#xff0c;林相跟大宝交代完为人处世的人生哲理之后&#xff0c;就要跟大宝告别了 在《庆余年 2》23集中&#xff0c;林相在告老还乡的路上与婉儿和大宝告别后 范闲也在与婉儿的对话中知道黑骑调动是绝密&#xff0c;并把最近一次告老还乡梅…...

大一C语言课设 服装销售系统 代码实现与项目总结

问题分析 服装信息管理及销售管理系统。方便对库存服装的信息管理和添加新服装数据&#xff0c;同时兼具库存数量管理功能。 功能实现 1、建立服装信息库&#xff0c;包括&#xff1a;服装代码、型号、规格、面料、颜色、单价、数量&#xff1b; 2、建立销售信息库&#xff…...

从新手到专家:深入探索JVM垃圾回收--开端篇

引言&#xff1a; 在Java的世界里&#xff0c;垃圾回收&#xff08;Garbage Collection, GC&#xff09;机制扮演着至关重要的角色&#xff0c;它决定了Java应用的性能、稳定性和扩展性。本系列文章旨在深入探讨JVM中的垃圾回收技术&#xff0c;从基础的概念讲起&#xff0c;直…...

R可视化:另类的柱状图

介绍 方格状态的柱状图 加载R包 knitr::opts_chunk$set(echo TRUE, message FALSE, warning FALSE) library(patternplot) library(png) library(ggplot2) library(gridExtra)rm(list ls()) options(stringsAsFactors F)导入数据 data <- read.csv(system.file(&qu…...

Docker的数据管理(数据卷+数据卷容器)

文章目录 一、Docker的数据管理1、概述2、主要的技术&#xff08;三种数据挂载方式&#xff09;2.1、数据卷&#xff08;Volumes&#xff09;2.2、绑定挂载&#xff08;Bind mounts&#xff09;2.3、tmpfs挂载&#xff08;Tmpfs mounts&#xff09;2.4、之间的关系&#xff08;…...

字符串-至多包含K种字符的子串中最长子串(mid)

一、题目描述 二、解题思路 借鉴以下题目思想&#xff0c;使用双指针&#xff0c;外层循环右侧指针移动&#xff0c;内存循环左侧指针移动 字符串-最长不含重复字符的子字符串(mid)-CSDN博客文章浏览阅读622次&#xff0c;点赞17次&#xff0c;收藏4次。java刷题&#xff1a;…...

Docker从安装开始精通

从虚拟机到容器 1.环境配置的难题 软件开发最大的麻烦事之一&#xff0c;就是环境配置。用户计算机的环境都不相同&#xff0c;你怎么知道自家的软件&#xff0c;能在那些机器跑起来&#xff1f; 用户必须保证两件事&#xff1a;操作系统的设置&#xff0c;各种库和组件的安装…...

MFC:初步理解序列化与反序列化(含代码实现)

序列化与反序列化是MFC将对象数据以二进制数据流的形式进行存储和读取的机制&#xff0c;读、写的效率很高。通过序列化与反序列化&#xff0c;可以将程序中对象在内存中数据保存到文件 (磁盘) 或者从文件 (磁盘) 中读取到内存以恢复对象数据&#xff0c;从而实现程序对数据的持…...

python程序控制结构

文章目录 一、python程序控制结构介绍二、顺序结构2.1、print()函数2.2、end参数2.3、input()函数 三、选择结构3.1选择结构的用途 四、循环结构4.1循环结构的构造4.1.1、循环结构的三个要素4.1.2、循环结构的一个要求4.1.3、循环结构的一个关系 4.2、循环语句4.2.1、while语句…...

【GD32】04 - Timer定时器

GD32中的定时器 GD32E230中有七个定时器&#xff0c;六种类型&#xff0c;其中通用的L4版本有两个&#xff0c;其他类型的各一个。 那我们就以通用L4这个类型来敲代码&#xff0c;其他流程是通用的。 通用L4 虽然每种类型的定时器都有自己的结构框图&#xff0c;但是其实大差…...

Golang | Leetcode Golang题解之第123题买卖股票的最佳时机III

题目&#xff1a; 题解&#xff1a; func maxProfit(prices []int) int {buy1, sell1 : -prices[0], 0buy2, sell2 : -prices[0], 0for i : 1; i < len(prices); i {buy1 max(buy1, -prices[i])sell1 max(sell1, buy1prices[i])buy2 max(buy2, sell1-prices[i])sell2 m…...

Leetcode2028. 找出缺失的观测数据

Every day a Leetcode 题目来源&#xff1a;2028. 找出缺失的观测数据 解法1&#xff1a;模拟 统计当前 m 个元素的总和 curSum sum(rolls)&#xff0c;总共 mn 个元素和为 total (m n) * mean。 排除 2 种情况&#xff1a; total - curSum > 6 * n&#xff1a;n 个…...

如何在CentOS中合理划分磁盘空间以优化系统性能

目录 前言 理想的分区方案 为什么需要单独分区 安全性 性能 管理和维护 稳定性和可靠性 升级和兼容性 结论 前言 在进行CentOS系统的安装和配置时&#xff0c;合理划分磁盘空间是确保系统性能、安全性和易于管理的关键步骤。本文将探讨如何根据系统的硬件配置和预期用途…...

算法(十一)贪婪算法

文章目录 算法简介算法概念算法举例 经典问题 -背包问题 算法简介 算法概念 贪婪算法&#xff08;Greedy&#xff09;是一种在每一步都采取当前状态下最好的或者最优的选择&#xff0c;从而希望导致结果也是全局最好或者最优的算法。贪婪算法是当下局部的最优判断&#xff0c…...

Rust之函数式语言特性:迭代器和闭包(一):概述

开发环境 Windows 11Rust 1.78.0 VS Code 1.89.1 项目工程 这次创建了新的工程minigrep. 函数式语言特性:迭代器和闭包 Rust的设计从许多现有语言和技术中获得了灵感&#xff0c;其中一个重要影响是函数式编程。函数式编程通常包括通过在参数中传递函数、从其他函数返回函数、…...

配置资源管理

一 Secret Secret 是用来保存密码、token、密钥等敏感数据的 k8s 资源&#xff0c;这类数据虽然也可以存放在 Pod 或者镜像中&#xff0c;但是放在 Secret 中是为了更方便的控制如何使用数据&#xff0c;并减少暴露的风险。 1 有三种类型&#xff1a; kubernetes.io/service…...

unity2020打包webGL时卡进程问题

我使用的2020.3.0f1c1&#xff0c;打包发布WEB版的时候会一直卡到asm2wasm.exe这个进程里&#xff0c;而且CPU占用率90%以上。 即使是打包一个新建项目的空场景也是同样的问题&#xff0c;我尝试过一直卡在这里会如何&#xff0c;结果还真打包成功了。只是打包一个空场景需要20…...

云原生架构相关技术_3.无服务器技术

1.技术特点 1.1面向特定领域的后端云服务&#xff08;BaaS&#xff09; 随着以Kubernetes为代表的云原生技术成为云计算的容器界面&#xff0c;Kubernetes成为云计算的新一代操作系统。面向特定领域的后端云服务&#xff08;BaaS&#xff09;则是这个操作系统上的服务API&…...

Leetcode:Z 字形变换

题目链接&#xff1a;6. Z 字形变换 - 力扣&#xff08;LeetCode&#xff09; 普通版本&#xff08;二维矩阵的直接读写&#xff09; 解决办法&#xff1a;直接依据题目要求新建并填写一个二维数组&#xff0c;最后再将该二维数组中的有效字符按从左到右、从上到下的顺序读取并…...

Python 3 判断文件是否存在

1 使用os.path模块 import osfile_path hello.txtif os.path.exists(file_path):print(f"文件 {file_path} 存在。") else:print(f"文件 {file_path} 不存在。") 2 使用pathlib模块 from pathlib import Pathfile_path Path(word.txt)if file_path.ex…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

react更新页面数据,操作页面,双向数据绑定

// 路由不是组件的直接跳转use client&#xff0c;useEffect&#xff0c;useRouter&#xff0c;需3个结合&#xff0c; use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...

CentOS 7.9安装Nginx1.24.0时报 checking for LuaJIT 2.x ... not found

Nginx1.24编译时&#xff0c;报LuaJIT2.x错误&#xff0c; configuring additional modules adding module in /www/server/nginx/src/ngx_devel_kit ngx_devel_kit was configured adding module in /www/server/nginx/src/lua_nginx_module checking for LuaJIT 2.x ... not…...

7种分类数据编码技术详解:从原理到实战

在数据分析和机器学习领域&#xff0c;分类数据&#xff08;Categorical Data&#xff09;的处理是一个基础但至关重要的环节。分类数据指的是由有限数量的离散值组成的数据类型&#xff0c;如性别&#xff08;男/女&#xff09;、颜色&#xff08;红/绿/蓝&#xff09;或产品类…...

盲盒一番赏小程序:引领盲盒新潮流

在盲盒市场日益火爆的今天&#xff0c;如何才能在众多盲盒产品中脱颖而出&#xff1f;盲盒一番赏小程序给出了答案&#xff0c;它以创新的玩法和优质的服务&#xff0c;引领着盲盒新潮流。 一番赏小程序的最大特色在于其独特的赏品分级制度。赏品分为多个等级&#xff0c;从普…...

Linux 中替换文件中的某个字符串

如果你想在 Linux 中替换文件中的某个字符串&#xff0c;可以使用以下命令&#xff1a; 1. 基本替换&#xff08;sed 命令&#xff09; sed -i s/原字符串/新字符串/g 文件名示例&#xff1a;将 file.txt 中所有的 old_text 替换成 new_text sed -i s/old_text/new_text/g fi…...