PyCharm专项训练5 最短路径算法
一、实验目的
本文的实验目的是通过编程实践，掌握并应用Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法来解决图论中的最短路径问题。
二、实验内容
- 数据准备：
- 使用邻接表的形式定义两个图
graph_dijkstra和graph_floyd，图中包含节点以及节点之间的边和对应的权重。
- 使用邻接表的形式定义两个图
- 算法实现：
- 实现Dijkstra算法，从指定的源节点（节点0）出发，计算并输出到图中其他所有节点的最短距离及路径。
- 实现Floyd算法，计算并输出图中任意两点之间的最短距离及路径。
- 结果输出：
- 对于Dijkstra算法，输出从源节点（节点0）到指定目标节点（如节点4）的最短距离和路径。
- 对于Floyd算法，输出图中任意两点（如节点0到节点4）之间的最短距离和路径，以验证算法的正确性和有效性。
三、实验演示
1.Dijkstra算法&实验结果截图：
#Dijkstra：import heapqdef dijkstra(graph, start):distances = {node: float('infinity') for node in graph}distances[start] = 0priority_queue = [(0, start)]previous_nodes = {node: None for node in graph}while priority_queue:current_distance, current_node = heapq.heappop(priority_queue)if current_distance > distances[current_node]:continuefor neighbor, weight in graph[current_node]:distance = current_distance + weightif distance < distances[neighbor]:distances[neighbor] = distanceprevious_nodes[neighbor] = current_nodeheapq.heappush(priority_queue, (distance, neighbor))return distances, previous_nodesdef get_path(previous_nodes, start, end):path = []while end is not None:path.append(end)end = previous_nodes[end]path.reverse()return path if path and path[0] == start else []# 图的表示（邻接表）
graph_dijkstra = {0: [(1,4), (7, 8)],1: [(0, 4), (7, 11), (2, 8)],2: [(1, 8), (8, 2), (3, 7),(5,4)],3: [(2,7 ), (5, 14), (4, 9)],4: [(3, 9),(5,10)],5: [(2,4),(3,14),(4,10),(6,2)],6: [(5,2),(7,1),(8,6)],7: [(0,8),(1,4),(6,1),(8,7)],8: [(2,2),(6,6),(7,7)]
}start_node = 0
end_node = 4
distances, previous_nodes = dijkstra(graph_dijkstra, start_node)print(f"从节点 {start_node} 到节点 {end_node} 的最短距离: {distances[end_node]}")
path = get_path(previous_nodes, start_node, end_node)
print(f"从节点 {start_node} 到节点 {end_node} 的最短路径: {path}")
2.Floyd算法&实验结果截图：
#Floyd
import heapq
def floyd_warshall(graph): num_nodes = len(graph) distances = [[float('inf')] * num_nodes for _ in range(num_nodes)] previous_nodes = [[-1] * num_nodes for _ in range(num_nodes)] for u in graph: for v, weight in graph[u]: distances[u][v] = weight previous_nodes[u][v] = u distances[v][u] = weight # 对于无向图 previous_nodes[v][u] = v for i in range(num_nodes): distances[i][i] = 0 for k in range(num_nodes): for i in range(num_nodes): for j in range(num_nodes): if distances[i][j] > distances[i][k] + distances[k][j]: distances[i][j] = distances[i][k] + distances[k][j] previous_nodes[i][j] = previous_nodes[k][j] return distances, previous_nodes def reconstruct_path(previous_nodes, start, end): path = [] while end != -1: path.append(end) end = previous_nodes[start][end] path.reverse() return path if path and path[0] == start else [] # 图的表示（邻接表）
graph_floyd = { 0: [(1,4), (7, 8)], 1: [(0, 4), (7, 11), (2, 8)], 2: [(1, 8), (8, 2), (3, 7),(5,4)], 3: [(2,7 ), (5, 14), (4, 9)], 4: [(3, 9),(5,10)],5: [(2,4),(3,14),(4,10),(6,2)],6: [(5,2),(7,1),(8,6)],7: [(0,8),(1,4),(6,1),(8,7)],8: [(2,2),(6,6),(7,7)]
} distances_floyd, previous_nodes_floyd = floyd_warshall(graph_floyd)
start_node = 0
end_node = 4 print(f"\n从节点 {start_node} 到节点 {end_node} 的最短距离: {distances_floyd[start_node][end_node]}")
path = reconstruct_path(previous_nodes_floyd, start_node, end_node)
print(f"从节点 {start_node} 到节点 {end_node} 的最短路径: {path}") 
相关文章：
PyCharm专项训练5 最短路径算法
一、实验目的 本文的实验目的是通过编程实践，掌握并应用Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法来解决图论中的最短路径问题。 二、实验内容 数据准备： 使用邻接表的形式定义两个图graph_dijkstra…...
“AI+Security”系列第4期（一）之“洞” 见未来：AI 驱动的漏洞挖掘新范式
在数字化浪潮下，安全漏洞问题日益严峻，成为各行业发展的重大挑战。近日，“AISecurity” 系列第 4 期线下活动于北京成功举办，聚焦 “洞” 见未来：AI 驱动的漏洞挖掘新范式，汇聚了安全领域的众多专家。 本次…...
安卓蓝牙扫描流程
目录 系统广播 流程图 源码跟踪 系统广播 扫描开启广播：BluetoothAdapter.ACTION_DISCOVERY_STARTED "android.bluetooth.adapter.action.DISCOVERY_STARTED";扫描关闭广播：BluetoothAdapter.ACTION_DISCOVERY_FINISHED "android.b…...
【视觉惯性SLAM：对极几何】
对极几何（Epipolar Geometry）介绍 对极几何是立体视觉中的核心内容之一，它描述了两个相机在观察同一个三维场景时，成像平面之间的几何关系。对极几何能够约束图像中对应点的位置关系，是双目立体匹配、三维重建、以及位…...
` 和 `Stream.toList()` 的区别（Java）)
Stream `Collectors.toList()` 和 `Stream.toList()` 的区别（Java）
Stream Collectors.toList() 和 Stream.toList() 的区别 问题背景 在以下代码中： Test void test() {JSONArray nodes new JSONArray();String[] names {"df1", "df2", "df3"};for (String name : names) {JSONObject obj new …...
【Python知识】Python面向对象编程知识
Python面向对象编程知识 概述1. 类（Class）2. 对象（Object）3. 封装（Encapsulation）4. 继承（Inheritance）5. 多态（Polymorphism）6. 抽象（Abstractio…...
安卓帧率获取
背景 性能优化，经常用到一些指标，诸如帧率、功耗等。对于普通app来讲， 之前一直使用gfxinfo指令获取丢帧率。但是这个指令无法获取游戏的帧率，查阅资料，发现SurfaceFlinger可以获取游戏帧率。 帧率获取原理 获取当前f…...
)
shell脚本(全)
shell脚本概述 第一个shell脚本 shell注释 shell变量 shell位置参数 shell字符串 shell内置命令 shell命令替换 输出 流程控制IF export命令 退出脚本 运行Shell脚本 实例导航 shell脚本概述 在说什么是shell脚本之前，先说说什么是shell。 从程序员的…...
Flask-----SQLAlchemy教程
存session session[username] username # 存储数据到 session 取session username session.get(username) render_template return render_template(index.html, usernameAlice)，渲染一个包含 username 变量的模板。 redirect return redirect(url_for(profil…...
【C++11】可变模板参数
目录 可变模板的定义方式 参数包的展开方式 递归的方式展开参数包 STL中的emplace相关接口函数 STL容器中emplace相关插入接口函数 编辑 模拟实现：emplace接口 C11的新特性可变参数模板能够让您创建可以接受可变参数的函数模板和类模板，相比 C9…...
.NET开发人员学习书籍推荐
作为一名.NET开发人员，掌握相关技术是提升开发能力和拓展职业发展的关键。无论你是刚入门的新人，还是希望精进技术的资深开发者，选择合适的学习资源至关重要。下面是一些经典且实用的学习书籍推荐，帮助你在C#、SQL、前端开发等方面…...
jupyter切换内核方法配置问题总结
下面这个博客总结了3种不同的方法，很有调理，推荐尝试 【最全指南】如何在 Jupyter Notebook 中切换/使用 conda 虚拟环境？ !!! 注意使用上面介绍的ipykernel方法2, 要在每一个希望被jupyter识别到的环境内【分别】安装ipykernel以及添加配置 …...
SVM理论推导
本文介绍支持向量机（SVM）的理论推导。 一、SVM 的基本思想 SVM 的目标是找到一个最优超平面，将样本分为不同的类别，并最大化类别间的间隔。 1. 线性可分情况下： 在特征空间中找到一个超平面，使得&#…...
如何永久解决Apache Struts文件上传漏洞
Apache Struts又双叒叕爆文件上传漏洞了。 自Apache Struts框架发布以来，就存在多个版本的漏洞，其中一些漏洞涉及到文件上传功能。这些漏洞可能允许攻击者通过构造特定的请求来绕过安全限制，从而上传恶意文件。虽然每次官方都发布补丁进行修…...
【Java数据结构与算法】第10-14章
第10章 树结构的基础部分 10.1 二叉树 10.1.1 为什么需要树这种数据结构 10.1.2 树示意图 10.1.3 二叉树的概念 10.1.4 二叉树遍历的说明 10.1.5 二叉树遍历应用实例(前序,中序,后序) 10.1.6 二叉树-查找指定节点 思路图解 10.1.7 二叉树-删除节点 package com.atguigu.tree;…...
MacOS M3源代码编译Qt6.8.1
编译时间过长，如果不想自己编译，可以通过如果网盘进行下载： 链接: https://pan.baidu.com/s/17lvF5jQ-vR6vE-KEchzrVA?pwdts26 提取码: ts26 在macOS上编译Qt 6需要一些前置步骤和工具。以下是编译Qt 6的基本步骤： 安装Xcode和…...
3.银河麒麟V10 离线安装Nginx
1. 下载nginx离线安装包 前往官网下载离线压缩包 2. 下载3个依赖 openssl依赖，前往 官网下载 pcre2依赖下载，前往Git下载 zlib依赖下载，前往Git下载 下载完成后完整的包如下： 如果网速下载不到请使用网盘下载 通过网盘分享的文件…...
实现 QTreeWidget 中子节点勾选状态的递归更新功能只影响跟节点的状态父节点状态不受影响
在 Qt 开发中，QTreeWidget 提供了树形结构的显示和交互功能。为了实现某个子节点勾选或取消勾选时，只影响当前节点及其子节点的状态，同时递归更新父节点的状态以正确显示 Qt::PartiallyChecked 或 Qt::Checked，我们可以借助 Qt 的…...
ubuntu24.04使用opencv4
ubuntu24.04LTS自带opencv4.5代码实例 //opencv_example.cpp #include <opencv2/opencv.hpp> #include <iostream>int main() {// 读取图像cv::Mat img cv::imread("image.jpg", cv::IMREAD_COLOR);if (img.empty()) {std::cerr << "无法读…...
R语言数据分析案例46-不同区域教育情况回归分析和探索
一、研究背景 教育是社会发展的基石，对国家和地区的经济、文化以及社会进步起着至关重要的作用。在全球一体化进程加速的今天，不同区域的教育发展水平呈现出多样化的态势。这种差异不仅体现在教育资源的分配上，还表现在教育成果、教育投入与…...
flink sink doris
接上文：一文说清flink从编码到部署上线 网上关于flink sink drois的例子较多，大部分不太全面，故本文详细说明，且提供完整代码。 flink doris版本对照表 1.添加依赖 <!--doris cdc--><!-- 参考："https…...
《探索 Apache Spark MLlib 与 Java 结合的卓越之道》
在当今大数据与人工智能蓬勃发展的时代，Apache Spark MLlib 作为强大的机器学习库，与广泛应用的 Java 语言相结合，为数据科学家和开发者们提供了丰富的可能性。那么，Apache Spark MLlib 与 Java 结合的最佳实践究竟是什么呢&#…...
Net9解决Spire.Pdf替换文字后，文件格式乱掉解决方法
官方文档 https://www.e-iceblue.com/Tutorials/Spire.PDF/Program-Guide/Text/Find-and-replace-text-on-PDF-document-in-C.html C# 在 PDF 中查找替换文本 原文件如下图，替换第一行的新编码，把41230441044替换为41230441000 替换代码如下ÿ…...
)
Kafka可视化工具 Offset Explorer (以前叫Kafka Tool)
数据的存储是基于 主题（Topic） 和 分区（Partition） 的 Kafka是一个高可靠性的分布式消息系统，广泛应用于大规模数据处理和实时, 为了更方便地管理和监控Kafka集群，开发人员和运维人员经常需要使用可视化工具…...
青少年编程与数学 02-004 Go语言Web编程 21课题、应用部署
青少年编程与数学 02-004 Go语言Web编程 21课题、应用部署 一、应用部署二、GoWeb部署到WINDOWS系统中1. 安装Go环境2. 创建并编写Go Web应用3. 初始化Go模块4. 编译Go Web应用5. 配置和运行Nginx6. 运行Go Web应用7. 访问应用总结 三、GoWeb部署到LINUX系统中1. 准备Linux服务…...
009-spring-bean的实例化流程
1 spring容器初始化时，将xml配置的bean 信息封装在 beandefinition对象 2 所有的beandefinition存储在 beandefinitionMap的map集合中 3 spring对map进行遍历，使用反射创建bean实例对象 4 创建好的bean存在名为singletonObjects的map集合中 5 调用ge…...
Timsort算法
Timsort算法是一种混合、稳定且高效的排序算法，源自归并排序和插入排序。它通过将已识别的子序列（称为“run”）与现有run合并直到满足某些条件来完成排序。以下是对Timsort算法的详细解释及举例说明： Timsort算法概述 混合性&…...
uniapp+vue 前端防多次点击表单，防误触多次请求方法。
最近项目需求写了个uniappvue前端H5,有个页面提交表单的时候发现会有用户乱点导致数据库多条重复脏数据。故需要优化，多次点击表单只请求一次。 思路: 直接调用uni.showToast，点完按钮跳一个提交成功的提示。然后把防触摸穿透mask设置成true就行&#…...
八、Hbase
Hbase 一、NoSQL非关系型数据库简介1.NoSQL 的起因2.NoSQL 的特点3.NoSQL 面临的挑战4.NoSQL 的分类 二、HBase数据库概述1.HBase数据库简介2.HBase数据模型简介3.HBase数据模型基本概念4.Hbase概念视图(逻辑视图)5.Hbase物理视图6.Hbase主要组件7.Hbase安装8.Hbase的数据读写流…...
ubuntu安装sublime安装与免费使用
1. ubuntu安装sublime 参考官网： Linux Package Manager Repositories 2. 破解过程 打开如下网址，打开/opt/sublime_text/sublime_text https://hexed.it/ 3. 替换在hexed打开的文件中查找并替换： 4180激活方法 使用二进制编辑器 8079 0500 0f94 c2替换为 c641 05…...
Onedrive精神分裂怎么办（有变更却不同步）
Onedrive有时候会分裂，你在本地删除文件，并没有同步到云端，但是本地却显示同步成功。 比如删掉了一个目录，在本地看已经删掉，onedrive显示已同步，但是别的电脑并不会同步到这个删除操作，在网页版…...
图像裁剪与批量推理：解决分割和变化检测中的大图处理问题
引言 在分割、变化检测等任务中，我们经常会遇到一个问题：模型的输入尺寸是固定且较小的（如256256或512512）。当需要处理分辨率较高的大图时，直接输入到模型中显然是不切实际的。那么，如何高效地解决这个问…...
第4章 函数
2024年12月25日一稿 4.1 函数的定义 4.1.1 函数和像 4.1.2 函数的性质 4.1.3 常用函数 4.2 复合函数和反函数 4.2.1 复合函数 4.2.2 反函数 4.3 特征函数与模糊子集 4.4 基数的概念 4.4.1 后继与归纳集 4.4.2 自然数，有穷集，无穷集 4.4.3 基数 4.5 可数…...
【JavaEE进阶】Spring传递请求参数
目录 🎍序言 🌴传递单个参数 🍀传递多个参数 🎄传递对象 🌳后端参数重命名（后端参数映射） 🚩ReuqestParam注解 🎍序言 访问不同的路径,就是发送不同的请求.在发送…...
在跨平台开发环境中构建高效的C++项目：从基础到最佳实践20241225
在跨平台开发环境中构建高效的C项目：从基础到最佳实践 引言 在现代软件开发中，跨平台兼容性和高效开发流程是每个工程师追求的目标。尤其是对于 C 开发者，管理代码的跨平台构建以及调试流程可能成为一项棘手的挑战。在本文中，我…...
无人零售及开源 AI 智能名片 S2B2C 商城小程序的深度剖析
摘要：本文聚焦无人零售这一新兴零售模式及其发展浪潮中崛起的开源 AI 智能名片 S2B2C 商城小程序。深入阐述无人零售的发展态势，细致剖析其驱动因素、现存问题，全面详细介绍小程序的功能特性、应用优势以及对无人零售的潜在价值，旨…...
PCL点云库入门——PCL库点云滤波算法之直通滤波（PassThrough）和条件滤波（ConditionalRemoval）
0、滤波算法概述 PCL点云库中的滤波算法是处理点云数据不可或缺的一部分，它们能够有效地去除噪声、提取特征或进行数据降维。例如，使用体素网格滤波（VoxelGrid）可以减少点云数据量，同时保留重要的形状特征。此外&#…...
v语言介绍
V 语言是一种多用途的编程语言，可以用于前端开发、后端开发、系统编程、游戏开发等多个领域。它的设计哲学是提供接近 C 语言的性能，同时简化开发过程并提高代码的安全性和可读性。接下来我会详细介绍 V 在前后端开发中的应用，并给出一个具体…...
GPT-O3：简单介绍
GPT-O3：人工智能领域的重大突破 近日，OpenAI发布了其最新的AI模型GPT-O3，这一模型在AGI评估中取得了惊人的成绩，展现出强大的能力和潜力。GPT-O3的出现标志着人工智能领域的重大进步，预计将在2025年实现更大的突破。 …...
重温设计模式--适配器模式
文章目录 适配器模式（Adapter Pattern）概述适配器模式UML图适配器模式的结构目标接口（Target）：适配器（Adapter）：被适配者（Adaptee）： 作用…...
API部署大模型
由于生产测试环境的服务器配置较低 不能够支撑大模型运行的配置 所以需要将大模型封装部署在A服务器上 在B服务器上进行调用 封装时可以使用FastAPI与Websocket两种通信方式进行通信 Websocket 在A服务器端部署大模型（服务端） import asyncio import …...
Linux -- 同步与条件变量
目录 同步 条件变量 pthread_cond_t pthread_cond_init（初始化条件变量） pthread_cond_destroy（销毁条件变量） pthread_cond_wait（线程等待条件变量） 重要提醒 pthread_cond_boardcast（…...
裸机篇----1.开发环境搭建)
Linux之ARM(MX6U)裸机篇----1.开发环境搭建
下载开启FTP服务 作用：用于电脑与linux系统之前文件传输 如上，编辑完成后重启 Window下FTP客户端安装使用http://www.filezilla.cn/download网址下载 新建网络连接站点 主机后写虚拟机的ip地址，用ifconfig查出ipv4的地址 笔记本电脑中虚拟…...
【C语言】结构体模块化编程
在模块化编程中，结构体作为数据存储的主要方式之一，它不仅用于存储数据，还帮助实现代码的封装与隐私保护。通过将结构体定义放在 .c 文件中并使用 get_ 和 set_ 函数进行访问，我们可以实现对结构体数据的保护，同时降低…...
SpringCloudAlibaba技术栈-Nacos
1、什么是Nacos？ Nacos是个服务中心，就是你项目每个功能模块都会有个名字，比如支付模块,我们先给这个模块起个名字就叫paymentService,然后将这个名字和这个模块的配置放到Nacos中，其他模块也是这样的。好处是这样能更好地管理项…...
Windows11家庭版启动Hyper-V
Hyper-V 是微软的硬件虚拟化产品，允许在 Windows 上以虚拟机形式运行多个操作系统。每个虚拟机都在虚拟硬件上运行，可以创建虚拟硬盘驱动器、虚拟交换机等虚拟设备。使用虚拟化可以运行需要较旧版本的 Windows 或非 Windows 操作系统的软件，以…...
《信管通低代码信息管理系统开发平台》Linux环境安装说明
1 简介 信管通低代码信息管理系统应用平台提供多环境软件产品开发服务，包括单机、局域网和互联网。我们专注于适用国产硬件和操作系统应用软件开发应用。为事业单位和企业提供行业软件定制开发，满足其独特需求。无论是简单的应用还是复杂的系统ÿ…...
第一节：电路连接【51单片机-L298N-步进电机教程】
摘要：本节介绍如何搭建一个51单片机L298N步进电机控制电路，所用材料均为常见的模块，简单高效的方式搭建起硬件环境 一、硬件清单 ①51单片机模块 ②恒流模块 ③开关电源 ④L298N模块 ⑤二相四线步进电机 ⑥电线若干 二、接线 三、L298N模…...
YoloDotNet 识别图像中特定关键点的位置
文章目录 1、初始化 Yolo 对象2、加载图像与检测关键点3、处理检测结果4、自定义关键点绘制和处理5、注意事项1、初始化 Yolo 对象 设置 YoloOptions，包括模型路径、模型类型（如果有专门的关键点检测模型类型则指定）、GPU 使用相关参数等。例如： var yoloOptions = new Yo…...
山景BP1048增加AT指令，实现单片机串口控制播放音乐（一）
1、设计目的 山景提供的SDK是蓝牙音箱demo，用户使用ADC按键或者IR遥控器，进行人机交互。然而现实很多场景，需要和单片机通信，不管是ADC按键或者IR接口都不适合和单片机通信。这里设计个AT指令用来和BP1048通信。AT指令如下图所示…...