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

计算机网络——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 算法的路由软件 实验内容 网络拓扑如图所示 实验过程 先编写开辟应该图的空间&#xff0c;然后给点映射数字&#xff0c;构建图。程序获取用户输入的学号&#xff0c;构建图中边的权值。接下来程序从用户输入获取最短路径的搜索起点&#xff0…...

AI智能化逐渐趋于成熟后,预测今后最吃香的开发职业

AI智能化正在成熟的路途中&#xff0c;这中间会有波折&#xff0c;但终有一天会来的&#xff0c;我相信等到了这一天&#xff0c;我们的开发效率和代码质量&#xff0c;将会大大不同&#xff0c;而我们的团队与个人&#xff0c;也会面临着很棒的体验。 那么在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

前言&#xff1a; vue项目&#xff0c;打包报错&#xff1a;CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory 报错现象&#xff1a; 报错原因&#xff1a; 这个错误是由Node.js在尝试分配内存时因为系统的可用内存不足而发生的。"JavaScript heap…...

计算机组成原理网课笔记

无符号整数的表示与运算 带符号整数的表示与运算 原反补码的特性对比 移码 定点小数...

Python学习第四部分 函数式编程

文章目录 高阶函数lambda 表达式和匿名函数偏函数闭包map函数reduce函数filter 函数sorted函数 函数式编程主要学习&#xff1a;高阶函数、闭包closure、匿名函数、偏函数&#xff0c;map函数、reduce函数、filter函数、sorted函数 函数式编程是个很古老的概念&#xff0c;最古…...

数据结构-二叉树-AVL树(平衡二叉树)

红黑树是平衡二叉树的一个变种。 一、 产生平衡二叉树的原因。 二叉搜索树的问题在于极端场景下退化为类似链表的结构&#xff0c;所以搜索的时间复杂度就变成了O(N)。为了保证二叉树不退化为链表&#xff0c;我们必须保证二叉树的的平衡性。 二叉平衡搜索树就是解决上面的问…...

【Qt问题】windeployqt如何提取Qt依赖库

往期回顾 【Qt问题】Qt Creator 如何链接第三方库-CSDN博客 【Qt问题】Qt 如何带参数启动外部进程-CSDN博客 【Qt问题】VS2019 Qt win32项目如何添加x64编译方式-CSDN博客 【Qt问题】windeployqt如何提取Qt依赖库 考虑这个问题主要是&#xff1a;当我们的程序运行好之后&#…...

VS2019下使用MFC完成科技项目管理系统

背景&#xff1a; &#xff08;一&#xff09;实验目的 通过该实验&#xff0c;使学生掌握windows程序设计的基本方法。了解科技项目组织管理的主要内容和管理方面的基本常识&#xff0c;熟练应用数据库知识&#xff0c;通过处理过程对计算机软件系统工作原理的进一步理解&…...

【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方式接收携带简单参数的请求 简单参数&#xff1a;参数名与形参变量名相同&#xff0c;定义形参即可接收参数。并且在接收过程中&#xff0c;会进行自动的类型转换。 启动应用程序后&#xff0c;在postman中进行测试&#xff1a; 请求成功&#xff0c;响应回了O…...

windows端口复用

1. 概述 使用 HTTP.sys 中的 Net.tcp Port Sharing 服务&#xff0c;配合 WinRM 实现端口复用。 优点&#xff1a; HTTP.sys 为 windows 原生机制&#xff0c; WinRM 为 windows 自带功能&#xff0c;动作较小&#xff0c;不易触发主 动防御。 需要管理员权限。 2. 原理 (…...

[Redis] 使用布隆过滤器和分布式锁实现用户注册

布隆过滤器&#xff08;Bloom Filter&#xff09;是一种数据结构&#xff0c;用于快速判断一个元素是否可能存在于一个集合中。它通过使用多个哈希函数和一个位数组来表示一个集合&#xff0c;当一个元素被加入到集合时&#xff0c;通过哈希函数计算出多个哈希值&#xff0c;并…...

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项目管理-大题【太原理工大学】

一、根据进度网络写出时间参数表、关键路径、总工期 此类题一般是给一个表&#xff0c;问三问。 第一问会问某个活动的时间参数&#xff0c;但我们需要把整个表都求出来&#xff0c;否则单求一个很困难&#xff08;如果你就是不想求整张表也行&#xff0c;不是硬性要求&#xf…...

【代码随想录】day48

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、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---》用户的登录&#xff0c;退出&#xff0c;注册。。。# 配置文件中配置&#xff1a;---》表会被迁移INSTALLED_APPS [django.contrib.auth,]# auth有哪些表---权限控制&#xff1a;-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…...

企业数字化转型走向平台化运营会经历哪些阶段?

蚓链实践总结企业数字化转型走向平台化运营通常会经历以下几个阶段&#xff1a; 1. 规划与准备阶段&#xff1a;明确转型目标和战略&#xff0c;评估现有业务和技术状况&#xff0c;制定转型计划。 2. 基础建设阶段&#xff1a;搭建数字化基础设施&#xff0c;包括云平台、数…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...