计算机网络——Dijkstra路由算法
实验目的
实现基于 Dijkstra 算法的路由软件
实验内容
网络拓扑如图所示
实验过程
先编写开辟应该图的空间,然后给点映射数字,构建图。程序获取用户输入的学号,构建图中边的权值。接下来程序从用户输入获取最短路径的搜索起点,然后运用dijkstra算法,计算最短路径然后输出,同时还会输出经过的点
关键代码
建图部分,先申请出这个图占用的空间,然后构建一个点到数字的映射,接着编写建图的函数划分学号中的数字来建图
std::vector<std::vector<int>> adj = {
// u, v, w, x, y, z {0, 0, 0, 0, 0, 0},// u{0, 0, 0, 0, 0, 0},// v{0, 0, 0, 0, 0, 0},// w{0, 0, 0, 0, 0, 0},// x{0, 0, 0, 0, 0, 0},// y{0, 0, 0, 0, 0, 0} // z
};std::unordered_map<char, int> toint = {{'u', 0}, {'v', 1}, {'w', 2}, {'x', 3}, {'y', 4}, {'z', 5}
};
std::unordered_map<int, char> tochar = {{0, 'u'}, {1, 'v'}, {2, 'w'}, {3, 'x'}, {4, 'y'}, {5, 'z'}
};void addlink(char num, char a, char b) {int add;if (num == '0') {add = 10;}else {add = (int)(num - '0');}adj[toint[a]][toint[b]] = add;adj[toint[b]][toint[a]] = add;
}
算法部分,编写dijkstra算法来查找最短路径,这里用到了优先队列的思想,同时还额外构建了两个相关,一个用于实时更新最短距离,一个用于存储经过的点
void dijkstra(int src, std::vector<int>& dist, std::vector<int>& prev) {int n = adj.size();dist.assign(n, INF);prev.assign(n, -1);dist[src] = 0;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;pq.push({0, src});while (!pq.empty()) {int v = pq.top().second;pq.pop();for (int u = 0; u < n; u++) {if (adj[v][u] != 0) {int new_dist = dist[v] + adj[v][u];if (new_dist < dist[u]) {dist[u] = new_dist;prev[u] = v;pq.push({new_dist, u});}}}}
}void printpath(int v, const std::vector<int>& prev, int end) {if (v < 0) return;printpath(prev[v], prev, end);if (end != v) {std::cout << tochar[v] << "-";}else {std::cout << tochar[v];}
}void printdijikstra(int start) {std::vector<int> dist, prev;dijkstra(start, dist, prev);for (int i = 1; i < adj.size(); i++) {printpath(i, prev, i);std::cout << ": " << dist[i] << std::endl;}
}
运行示例


程序在输入了学号之后,自动更具拓扑结构建图,输出邻接矩阵。然后用户输入最短路径的起点,然后程序调用dijkstra算法计算从起点到其他的点的最端路径然后输出,同时会输出经过的点
完整代码
BJTU_CS_Learning/computernetwork/dijkstra.cpp at main · JJLi0427/BJTU_CS_Learning (github.com)
相关文章:
计算机网络——Dijkstra路由算法
实验目的 实现基于 Dijkstra 算法的路由软件 实验内容 网络拓扑如图所示 实验过程 先编写开辟应该图的空间,然后给点映射数字,构建图。程序获取用户输入的学号,构建图中边的权值。接下来程序从用户输入获取最短路径的搜索起点࿰…...
AI智能化逐渐趋于成熟后,预测今后最吃香的开发职业
AI智能化正在成熟的路途中,这中间会有波折,但终有一天会来的,我相信等到了这一天,我们的开发效率和代码质量,将会大大不同,而我们的团队与个人,也会面临着很棒的体验。 那么在AI智能化真正趋于成…...
Acwing2024蓝桥杯BFS
AcWing 1355. 母亲的牛奶 bfs: #include<iostream> #include<queue> using namespace std; const int N21; int A,B,C; bool flag[N][N][N]; struct node{int a,b,c; }; queue<node>q; void check(int a,int b,int c){if(!flag[a][b][c]){q.push({a,b,c})…...
vue打包报错:CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
前言: vue项目,打包报错:CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory 报错现象: 报错原因: 这个错误是由Node.js在尝试分配内存时因为系统的可用内存不足而发生的。"JavaScript heap…...
计算机组成原理网课笔记
无符号整数的表示与运算 带符号整数的表示与运算 原反补码的特性对比 移码 定点小数...
Python学习第四部分 函数式编程
文章目录 高阶函数lambda 表达式和匿名函数偏函数闭包map函数reduce函数filter 函数sorted函数 函数式编程主要学习:高阶函数、闭包closure、匿名函数、偏函数,map函数、reduce函数、filter函数、sorted函数 函数式编程是个很古老的概念,最古…...
数据结构-二叉树-AVL树(平衡二叉树)
红黑树是平衡二叉树的一个变种。 一、 产生平衡二叉树的原因。 二叉搜索树的问题在于极端场景下退化为类似链表的结构,所以搜索的时间复杂度就变成了O(N)。为了保证二叉树不退化为链表,我们必须保证二叉树的的平衡性。 二叉平衡搜索树就是解决上面的问…...
【Qt问题】windeployqt如何提取Qt依赖库
往期回顾 【Qt问题】Qt Creator 如何链接第三方库-CSDN博客 【Qt问题】Qt 如何带参数启动外部进程-CSDN博客 【Qt问题】VS2019 Qt win32项目如何添加x64编译方式-CSDN博客 【Qt问题】windeployqt如何提取Qt依赖库 考虑这个问题主要是:当我们的程序运行好之后&#…...
VS2019下使用MFC完成科技项目管理系统
背景: (一)实验目的 通过该实验,使学生掌握windows程序设计的基本方法。了解科技项目组织管理的主要内容和管理方面的基本常识,熟练应用数据库知识,通过处理过程对计算机软件系统工作原理的进一步理解&…...
【Android】Kotlin学习之数据容器(数组for循环遍历)
数组遍历 1. for ( item in arr){…} 2. for ( i in arr.indeces ) {…} (遍历下标) 3. for ((index, item) in arr.withInfex()) {…} (遍历下标和元素) 4. arr.forEach {} ( 遍历元素 ) 5. arr.forEachIndexed{index, item -> …}...
JavaWeb_请求响应_简单参数实体参数
一、SpringBoot方式接收携带简单参数的请求 简单参数:参数名与形参变量名相同,定义形参即可接收参数。并且在接收过程中,会进行自动的类型转换。 启动应用程序后,在postman中进行测试: 请求成功,响应回了O…...
windows端口复用
1. 概述 使用 HTTP.sys 中的 Net.tcp Port Sharing 服务,配合 WinRM 实现端口复用。 优点: HTTP.sys 为 windows 原生机制, WinRM 为 windows 自带功能,动作较小,不易触发主 动防御。 需要管理员权限。 2. 原理 (…...
[Redis] 使用布隆过滤器和分布式锁实现用户注册
布隆过滤器(Bloom Filter)是一种数据结构,用于快速判断一个元素是否可能存在于一个集合中。它通过使用多个哈希函数和一个位数组来表示一个集合,当一个元素被加入到集合时,通过哈希函数计算出多个哈希值,并…...
Okhttp 发送https请求,忽略ssl认证
工具类 import lombok.extern.slf4j.Slf4j;import javax.net.ssl.HostnameVerifier; import javax.net.ssl.SSLContext; import javax.net.ssl.SSLSocketFactory; import javax.net.ssl.TrustManager; import javax.net.ssl.TrustManagerFactory; import javax.net.ssl.X509Tru…...
IT项目管理-大题【太原理工大学】
一、根据进度网络写出时间参数表、关键路径、总工期 此类题一般是给一个表,问三问。 第一问会问某个活动的时间参数,但我们需要把整个表都求出来,否则单求一个很困难(如果你就是不想求整张表也行,不是硬性要求…...
【代码随想录】day48
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一、198打家劫舍二、213打家劫舍II三、337打家劫舍III 一、198打家劫舍 class Solution { public:int rob(vector<int>& nums) {vector<int> dp(n…...
【补充】1-auth的使用、扩写auth的user表、django支持缓存
1 Auth的使用 1.1 扩写auth的user表 2 缓存 1 Auth的使用 # django 的一个app---》用户的登录,退出,注册。。。# 配置文件中配置:---》表会被迁移INSTALLED_APPS [django.contrib.auth,]# auth有哪些表---权限控制:-Permission&a…...
力扣-21. 合并两个有序链表-js实现
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/ /*** param {ListNode} list1* param {ListNode} list2* return {ListNode}*/ const mergeTwoList…...
tensorflow报错
参考 TensorFlow binary is optimized to use available CPU instructions in performance-critical operations._this tensorflow binary is optimized to use availab-CSDN博客 解决Python中cuBLAS插件无法注册问题_unable to register cudnn factory: attempting to re-CS…...
企业数字化转型走向平台化运营会经历哪些阶段?
蚓链实践总结企业数字化转型走向平台化运营通常会经历以下几个阶段: 1. 规划与准备阶段:明确转型目标和战略,评估现有业务和技术状况,制定转型计划。 2. 基础建设阶段:搭建数字化基础设施,包括云平台、数…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
