Qt地铁智慧换乘系统浅学( 三 )最少路径和最少换乘实现

本算法全都基于广度优先

  • 概念
  • 最短路径实现
    • 所用容器
    • 算法思路
  • 最少换乘实现
    • 所需容器
    • 算法思路
  • 成果展示
  • 代码实现
    • 判断是最短路径还是最少换乘
    • 最短路径代码实现
    • 最少换乘代码实现
    • 根据所得List画出线路
  • ui界面的维护(前提条件)
    • 界面
    • 初始化combox控件
    • 建立槽函数

概念

概念这里不过多介绍,很多文章介绍
大体意思是队列思想,每次入队相邻的节点,按照队列以此调用
这里如果想要实现最短路,最少换乘的话,需要用到优先队列
在以上的基础上,对队列进行dist距离的排序,或者trans换乘次数的排序
每次去除最少的,也类似于贪心

最短路径实现

所用容器

typedef std::pair<int,int> PII;  //dist trans
typedef std::pair<QString,QString> nodea; //stationname linename
typedef std::pair<PII,nodea> PLL;  //dist trans ..... ....
QMap<QString,int> dist; //距离表
QMap<QString,int> trans; //换乘
QMap<nodea,bool> final; //是否遍历过
QMap<QString,nodea>pre;  //父节点维护
std::priority_queue<PLL,std::vector<PLL >, std::greater<PLL > > q;  ///优先队列 每次取dist最少的节点

算法思路

这里我们实现了最短路径下最少换乘


1 将换乘表 和 距离表全部设置为INTMAX2 将起点的 换成表 和 距离表 设置为 0
3 将出发站信息存储到优先队列q中 { {00}{startstr , linename} } 注意(出发点可能有多个,出发点有可能属于多个线路)
4 将pre[startstr]赋值为{ "00","00"} 方便还原路径时截止
5 进入while循环 每次取top值 ,为换乘最少的站 ,判断final[top.second]是否为true,如果已经遍历过 那么continue ,否则 final[top.second] = true
6 遍历这个站临近的站点 l , 然后遍历站点i 与 l 所属的线路 k  我们设nodea j ={ l,k}   这时候我们讨论  设now = top.second
(1) 如果dist[j.first] > dist[now .first] + dp[now.first][j.first]  则更新 ,   pre[j.first] = now;如果大于则 更新 ,并且 pre[j.frist] =  now ; 距离表同样也更新 然后入队列(2) 如果dist[j.first] == dist[now .first] + dp[now.first][j.first]我们需要判断换乘最少!如果k==now.second 说明不需要换乘 我们判断trans[j.first] 是否大于 trans[now.first]即可  如果大于则更新如果k!=now.second 说明需要换乘 我们判断trans[j.first] 是否大于 trans[now.first]+1 即可 如果大于则更新7 最后等待while执行完毕 我们获得了 pre[ endstr ]的信息,然后循环调用pre 直到00结束

最少换乘实现

所需容器

QMap<QString,int> dist; //距离表QMap<QString,int> trans; //换乘QMap<nodea,bool> final; //是否遍历过typedef std::pair<int,int> PII;  //换乘 距离typedef std::pair<QString,QString> nodea; //站点名 和 线路名typedef std::pair<PII,nodea> PLL; // 某个站点的换成次数 和 距离 以及父站点和所属线路QMap<QString,nodea>pre;  //还原最少换乘的工具std::priority_queue<PLL,std::vector<PLL >, std::greater<PLL > > q; //优先队列 优先使用换乘最少的站点

算法思路

算法思路1 将换乘表 和 距离表全部设置为INTMAX2 将起点的 换成表 和 距离表 设置为 0
3 将出发站信息存储到优先队列q中 { {00}{startstr , linename} } 注意(出发点可能有多个,出发点有可能属于多个线路)
4 将pre[startstr]赋值为{ "00","00"} 方便还原路径时截止
5 进入while循环 每次取top值 ,为换乘最少的站 ,判断final[top.second]是否为true,如果已经遍历过 那么continue ,否则 final[top.second] = true
6 遍历这个站临近的站点 l , 然后遍历站点i 与 l 所属的线路 k  我们设nodea j ={ l,k}      这时候我们讨论  设now = top.second
(1)如果站点i的线路 与 k 一样 那么换乘次数不会增加 这个时候我们判断 trans[j.first] 是否大于 trans[i] 如果大于则 更新 ,并且 pre[j.frist] =  now ; 距离表同样也更新 然后入队列如果 换乘次数相等的话  我们判断距离表 , 如果dist[j.first] > dist[now .first] + dp[now.first][j.first]则更新 pre[j.first] = now;(2) 如果站点i的线路 与 k不一样 那么我们的换乘就有可能+1这个时候我们判断trans[j.first]  是否大于 trans[now.frist] +1 如果大于 则更新 并且 pre[j.first] = { now.first,k} ; 距离表同样也更新 这里如果pre[j.frist] = now就会出错,问题在后续讲解如果 transp[j.irst]  == trans[now.first] +1  我们就判断距离表 如果dist[j.first] > dist[now .first] + dp[now.first][j.first] 则更新,pre[j.first] = {now.first,k} 
7 最后等待while执行完毕 我们获得了 pre[ endstr ]的信息,然后循环调用pre 直到00结束

成果展示

在这里插入图片描述

代码实现

判断是最短路径还是最少换乘

void ChooseShortorLessPath(QGraphicsView *graphicsView,QString startstr,QString endstr,QRadioButton *sht,QRadioButton *less,QTextBrowser *textBrowser){qDebug()<<"选择开始\n";if(startstr.size()==0||endstr.size()==0){QMessageBox MyBox(QMessageBox::Warning,"警告","请选择站点",QMessageBox::Yes|QMessageBox::No);MyBox.exec();return;}QMap<QString, node>::iterator it = Station.find(startstr);if (it == Station.end()) {QMessageBox MyBox(QMessageBox::Warning,"警告","输入站点有误",QMessageBox::Yes|QMessageBox::No);MyBox.exec();return;}it =Station.find(endstr);if (it == Station.end()) {QMessageBox MyBox(QMessageBox::Warning,"警告","输入站点有误",QMessageBox::Yes|QMessageBox::No);MyBox.exec();return;}if(startstr == endstr){QMessageBox MyBox(QMessageBox::Warning,"警告","请不要输入相同站点 ",QMessageBox::Yes|QMessageBox::No);MyBox.exec();return;}if(sht->isChecked()) getshortTimePath(graphicsView,startstr,endstr,textBrowser);if(less->isChecked()) getlessTransPath(graphicsView,startstr,endstr,textBrowser);}

最短路径代码实现

typedef std::pair<int,int> PII;
typedef std::pair<QString,QString> nodea;
typedef std::pair<PII,nodea> PLL;void getshortTimePath(QGraphicsView *graphicsView,const QString startstr,const QString endstr,QTextBrowser *textBrowser){qDebug()<<"选择成功\n";const int IntMax = INT32_MAX;QMap<QString,int> dist; //距离表QMap<QString,int> trans; //换乘QMap<nodea,bool> final; //是否遍历过for(auto i:Station.keys()){dist[i] = IntMax;trans[i] = IntMax;}QMap<QString,nodea>pre;pre[startstr] = nodea{"00","00"};std::priority_queue<PLL,std::vector<PLL >, std::greater<PLL > > q;for(auto i:Station_Line[startstr]){q.push(PLL{{0,0},nodea{startstr,i}});}dist[startstr] = 0;trans[startstr] = 0;qDebug()<<"初始化完成\n";while(q.size()){PLL f= q.top();q.pop();nodea now = f.second;if(final[now]) continue;final[now] = true;for(auto i:edge[now.first]){ //相邻的站点for(auto j:mp[now.first][i]){ //和相邻站点共有的线路qDebug()<<now.first<<"-----"<<i<<"----"<<j<<" \n ";nodea newnodea = nodea{i,j};if(final[newnodea]) continue;if(dist[i] > dist[i]+dp[now.first][i]){dist[i] = dist[i]+dp[now.first][i];qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";if(j == now.second){ trans[i] = trans[now.first];  pre[i] = now; }else {trans[i] = trans[now.first] + 1; pre[i] = nodea{now.first,j}; }qDebug()<<i<<"---"<<pre[i]<<" \n ";q.push(PLL{PII{dist[i],trans[i]},newnodea});}else if(dist[i] == dist[now.first]+dp[now.first][i]){if(j == now.second){if(trans[i] > trans[now.first]){trans[i] = trans[now.first];pre[i] = now;q.push(PLL{PII{dist[i],trans[i]},newnodea});}}if(j != now.second){if(trans[i] > trans[now.first] + 1 ){trans[i] = trans[now.first] + 1;pre[i] = nodea{now.first,j};q.push(PLL{PII{dist[i],trans[i]},newnodea});}}}}}}qDebug()<<"最短路执行完毕\n";QList<nodea>s;int t=0;nodea u = pre[endstr];while(u.second!="00"){s.append(u);qDebug()<<"---"<<u.first<<" \n ";u=pre[u.first];t++;if(t>40) return;}qDebug()<<"还原成功\n";drawpath(graphicsView,startstr,endstr,s,textBrowser);
}

最少换乘代码实现

void getlessTransPath(QGraphicsView *graphicsView ,const QString startstr,const QString endstr,QTextBrowser *textBrowser){qDebug()<<"选择成功\n";const int IntMax = INT32_MAX;QMap<QString,int> dist; //距离表QMap<QString,int> trans; //换乘QMap<nodea,bool> final; //是否遍历过for(auto i:Station.keys()){trans[i] = IntMax;dist[i] = IntMax;}QMap<QString,nodea>pre;pre[startstr] = nodea{"00","00"};std::priority_queue<PLL,std::vector<PLL >, std::greater<PLL > > q;for(auto i:Station_Line[startstr]){q.push(PLL{{0,0},nodea{startstr,i}});}dist[startstr] = 0;trans[startstr] = 0;qDebug()<<"初始化完成\n";while(q.size()){PLL f= q.top();q.pop();nodea now = f.second;if(final[now]) continue;final[now] = true;for(auto i:edge[now.first]){ //相邻的站点for(auto j:mp[now.first][i]){ //和相邻站点共有的线路qDebug()<<now.first<<"-----"<<i<<"----"<<j<<" \n ";nodea newnodea = nodea{i,j};if(final[newnodea]) continue;if(j == now.second){if(trans[i] > trans[now.first]){dist[i] = dist[now.first] + dp[now.first][i];trans[i] = trans[now.first];pre[i] = now;q.push(PLL{PII{trans[i],dist[i]},newnodea});qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";}else if(trans[i] == trans[now.first]){if(dist[i] > dist[now.first]+dp[now.first][i]){dist[i] = dist[now.first]+dp[now.first][i];qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";pre[i] = now;q.push(PLL{PII{trans[i],dist[i]},newnodea});}}}if(j != now.second){if(trans[i] > trans[now.first] + 1 ){trans[i] = trans[now.first] + 1;dist[i] = dist[now.first] + dp[now.first][i];pre[i] = nodea{now.first,j};q.push(PLL{PII{trans[i],dist[i]},newnodea});qDebug()<<now.first<<"---"<<i<<"......."<<now<<" \n ";}else if(trans[i] == trans[now.first] + 1 ){if(dist[i] > dist[now.first]+dp[now.first][i]){dist[i] = dist[now.first]+dp[now.first][i];qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";pre[i] = nodea{now.first,j};q.push(PLL{PII{trans[i],dist[i]},newnodea});}}}}}}qDebug()<<"最短路执行完毕\n";QList<nodea>s;int t=0;nodea u = pre[endstr];while(u.second!="00"){s.append(u);qDebug()<<"---"<<u.first<<" \n ";u=pre[u.first];t++;if(t>40) return;}qDebug()<<"还原成功\n";drawpath(graphicsView,startstr,endstr,s,textBrowser);
}

根据所得List画出线路

void getlessTransPath(QGraphicsView *graphicsView ,const QString startstr,const QString endstr,QTextBrowser *textBrowser){qDebug()<<"选择成功\n";const int IntMax = INT32_MAX;QMap<QString,int> dist; //距离表QMap<QString,int> trans; //换乘QMap<nodea,bool> final; //是否遍历过for(auto i:Station.keys()){trans[i] = IntMax;dist[i] = IntMax;}QMap<QString,nodea>pre;pre[startstr] = nodea{"00","00"};std::priority_queue<PLL,std::vector<PLL >, std::greater<PLL > > q;for(auto i:Station_Line[startstr]){q.push(PLL{{0,0},nodea{startstr,i}});}dist[startstr] = 0;trans[startstr] = 0;qDebug()<<"初始化完成\n";while(q.size()){PLL f= q.top();q.pop();nodea now = f.second;if(final[now]) continue;final[now] = true;for(auto i:edge[now.first]){ //相邻的站点for(auto j:mp[now.first][i]){ //和相邻站点共有的线路qDebug()<<now.first<<"-----"<<i<<"----"<<j<<" \n ";nodea newnodea = nodea{i,j};if(final[newnodea]) continue;if(j == now.second){if(trans[i] > trans[now.first]){dist[i] = dist[now.first] + dp[now.first][i];trans[i] = trans[now.first];pre[i] = now;q.push(PLL{PII{trans[i],dist[i]},newnodea});qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";}else if(trans[i] == trans[now.first]){if(dist[i] > dist[now.first]+dp[now.first][i]){dist[i] = dist[now.first]+dp[now.first][i];qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";pre[i] = now;q.push(PLL{PII{trans[i],dist[i]},newnodea});}}}if(j != now.second){if(trans[i] > trans[now.first] + 1 ){trans[i] = trans[now.first] + 1;dist[i] = dist[now.first] + dp[now.first][i];pre[i] = nodea{now.first,j};q.push(PLL{PII{trans[i],dist[i]},newnodea});qDebug()<<now.first<<"---"<<i<<"......."<<now<<" \n ";}else if(trans[i] == trans[now.first] + 1 ){if(dist[i] > dist[now.first]+dp[now.first][i]){dist[i] = dist[now.first]+dp[now.first][i];qDebug()<<now.first<<"---"<<i<<"......."<<dist[i]<<" \n ";pre[i] = nodea{now.first,j};q.push(PLL{PII{trans[i],dist[i]},newnodea});}}}}}}qDebug()<<"最短路执行完毕\n";QList<nodea>s;int t=0;nodea u = pre[endstr];while(u.second!="00"){s.append(u);qDebug()<<"---"<<u.first<<" \n ";u=pre[u.first];t++;if(t>40) return;}qDebug()<<"还原成功\n";drawpath(graphicsView,startstr,endstr,s,textBrowser);
}

ui界面的维护(前提条件)

界面

在这里插入图片描述

初始化combox控件

void initcombox(QComboBox *combox1,QComboBox *combox2){QStringList sta_name_list;for(auto &i:Station.keys())sta_name_list.append(i);std::sort(sta_name_list.begin(),sta_name_list.end(),[](const QString &s1, const QString &s2){return (s1.localeAwareCompare(s2) < 0);});combox1->addItems(sta_name_list);combox2->addItems(sta_name_list);QLineEdit *line1 = new QLineEdit;combox1->setLineEdit(line1);combox1->lineEdit()->clear();QLineEdit *line2 = new QLineEdit;combox2->setLineEdit(line2);combox2->lineEdit()->clear();
}

建立槽函数

connect(ui->pushButton,&QPushButton::clicked,this,[=]{ChooseShortorLessPath(ui->graphicsView,ui->comboBox->lineEdit()->text(),ui->comboBox_2->lineEdit()->text(),ui->radioButton,ui->radioButton_2,ui->textBrowser);});

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/140918.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java中的数组

1.数组的概念 数组概念&#xff1a; 数组就是用于存储数据的长度固定的容器&#xff0c;保证多个数据的数据类型要一致。 百度百科中对数组的定义&#xff1a; 所谓数组(array)&#xff0c;就是相同数据类型的元素按一定顺序排列的集合&#xff0c;就是把有限个类型相同的变…

Redis核心数据结构实战与高性能解析

目录 一、安装Redis 二、Redis线程与高性能 2.1 Redis是单线程么&#xff1f; 2.2 Redis读写是单线程为何这么快&#xff1f; 2.3 Redis如何处理并发操作命令&#xff1f; 三、核心数据结构实战 3.1 字符串常用操作实战 SET 存入键值对 SETNX SETEX MSET 批量存入键…

华为云云耀云服务器L实例评测|华为云上安装kafka

文章目录 华为云云耀云服务器L实例评测&#xff5c;华为云上安装kafka一、kafka介绍二、华为云主机准备三、kafka安装1. 安装什么版本java2. 安装zookeeper服务3. 使用systemctl 管理启动ZooKeeper服务4. 修改kafka配置5. 使用systemctl 管理启动kafka服务6. 创建一个测试 topi…

Vue路由及Node.js环境搭建

目录 一.Vue路由 1.1 定义 1.2 应用领域 1.3 代码展示 二、Node.js 2.1 定义 2.2 特点 三.Node.js安装与配置 3.1.下载 3.2.安装 3.3.环境搭建 好啦今天到这了&#xff0c;希望帮到你&#xff01;&#xff01;&#xff01; 一.Vue路由 1.1 定义 Vue路由是指使用Vue Router…

大数据-hadoop

1.hadoop介绍 1.1 起源 1.2 版本 1.3生产环境版本选择 Hadoop三大发行版本:Apache、Cloudera、Hortonworks Apache版本最原始的版本 Cloudera在大型互联网企业中用的较多 Hortonworks文档较好 1.4架构 hadoop由三个模块组成 分布式存储HDFS 分布式计算MapReduce 资源调度引擎Y…

单片机上软字库换32进制存储,空间占用少20%

在之前的单片机字库建立的推送中: https://blog.csdn.net/platform/article/details/130742775&#xff0c; 存储了GB2312字符集对应的软字库文件&#xff0c;在16*16的编码下总字库的507KB&#xff0c;后来把字体切换成了12*12&#xff0c;软字库缩减到了301KB。当然这里面对…

Android---底部弹窗之BottomSheetDialog

BottomSheetDialog 是Android开发中的一个弹出式对话框&#xff0c;它从屏幕底部弹出并覆盖部分主界面。 1. BottomSheetDialog的使用 // 参数2&#xff1a;设置BottomSheetDialog的主题样式&#xff1b;将背景设置为transparent&#xff0c;这样我们写的shape_bottom_sheet_…

20230918使用ffmpeg将mka的音频转为AAC编码以便PR2023来识别

20230918使用ffmpeg将mka的音频转为AAC编码以便PR2023来识别 2023/9/18 20:58 ffmpeg -i 1.mka -acodec aac 1.mp4 ffmpeg -i 1.mka -vn -c:a aac 2.aac ffmpeg -i 1.mka -vn -c:a aac 2.MP4 ffmpeg mka 转 aacmp4 https://avmedia.0voice.com/?id42526 用ffmpeg将mka格式转化…

华为云云耀云服务器L实例评测 | Docker 部署 Reids容器

文章目录 一、使用Docker部署的好处二、Docker 与 Kubernetes 对比三、云耀云服务器L实例 Docker 部署 Redis四、可视化工具连接Redis⛵小结 一、使用Docker部署的好处 Docker的好处在于&#xff1a;在不同实例上运行相同的容器 Docker的五大优点&#xff1a; 持续部署与测试…

AI绘图提示词Stable Diffusion Prompt 笔记

基础 提示词分为正向提示词&#xff08;positive prompt&#xff09;和反向提示词&#xff08;negative prompt&#xff09;&#xff0c;用来告诉AI哪些需要&#xff0c;哪些不需要词缀的权重默认值都是1&#xff0c;从左到右依次减弱&#xff0c;权重会影响画面生成结果。AI …

Spring Boot集成Redis实现数据缓存

🌿欢迎来到@衍生星球的CSDN博文🌿 🍁本文主要学习Spring Boot集成Redis实现数据缓存 🍁 🌱我是衍生星球,一个从事集成开发的打工人🌱 ⭐️喜欢的朋友可以关注一下🫰🫰🫰,下次更新不迷路⭐️💠作为一名热衷于分享知识的程序员,我乐于在CSDN上与广大开发者…

C++标准模板库STL——list的使用及其模拟实现

1.list的介绍 list的文档介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向链表结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向 其前一个…

【C++】开源:单元测试框架gtest配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍单元测试框架gtest配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff…

服务器性能测试监控平台export+prometheus(普罗米修斯)+grafana搭建

1. export 数据采集工具 简介&#xff1a; export是prometheus是的数据采集组件的总称&#xff0c;它可以将采集到的数据转为prometheus支持的格式 node_export: 用来监控服务器硬件资源的采集器&#xff0c;端口号为9100mysql_export: 用来监控mysql数据库资源的采集器&…

性能测试 —— Tomcat监控与调优:Jconsole监控

JConsole的图形用户界面是一个符合Java管理扩展(JMX)规范的监测工具&#xff0c;JConsole使用Java虚拟机(Java VM)&#xff0c;提供在Java平台上运行的应用程序的性能和资源消耗的信息。在Java平台&#xff0c;标准版(Java SE平台)6&#xff0c;JConsole的已经更新到目前的外观…

前端新轮子Nue,号称替代Vue、React和Svelte

新的简约前端开发工具集Nue.js 于周三发布。在 Hacker News 上介绍它时&#xff0c;前端开发者和Nue.js 的创作者Tero Piirainen表示&#xff0c;它是 React、Vue、Next.js、Vite、Svelte 和 Astro 的替代品。他在 Nue.js的 FAQ 中进一步解释说&#xff0c;它是为网站和响应式用…

力扣刷题-链表-两两交换链表中的节点

24.两两交换链表中的节点 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 解题思路 采用正常模拟的方法。 建议使用虚拟头结点&#xff0c;这样会方便很多&am…

【python爬虫】爬虫所需要的爬虫代理ip是什么?

目录 前言 一、什么是爬虫代理 IP 二、代理 IP 的分类 1.透明代理 2.匿名代理 3.高匿代理 三、如何获取代理 IP 1.免费代理网站 2.付费代理服务 四、如何使用代理 IP 1.使用 requests 库 2.使用 scrapy 库 五、代理 IP 的注意事项 1.代理 IP 可能存在不稳定性 2…

R语言贝叶斯非参数模型:密度估计、非参数化随机效应META分析心肌梗死数据...

全文链接&#xff1a;http://tecdat.cn/?p23785 最近&#xff0c;我们使用贝叶斯非参数&#xff08;BNP&#xff09;混合模型进行马尔科夫链蒙特卡洛&#xff08;MCMC&#xff09;推断&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 概述 相关视频 在这篇文…

坐标休斯顿,TDengine 受邀参与第九届石油天然气数字化大会

美国中部时间 9 月 14 日至 15 日&#xff0c;第九届石油天然气数字化大会在美国德克萨斯州-休斯顿-希尔顿美洲酒店举办。本次大会汇聚了数百名全球石油天然气技术高管及众多极具创新性的数据技术方案商&#xff0c;组织了上百场硬核演讲&#xff0c;技术专家与行业从业者共聚一…