-
Qt地铁智慧换乘系统浅学（ 三 ）最少路径和最少换乘实现
概念
概念这里不过多介绍，很多文章介绍
大体意思是队列思想，每次入队相邻的节点，按照队列以此调用
这里如果想要实现最短路，最少换乘的话，需要用到优先队列
在以上的基础上，对队列进行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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
算法思路
这里我们实现了最短路径下最少换乘
1 将换乘表 和 距离表全部设置为INTMAX 2 将起点的 换成表 和 距离表 设置为 0 3 将出发站信息存储到优先队列q中 { {0，0} ， {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结束- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
最少换乘实现
所需容器
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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
算法思路
算法思路 1 将换乘表 和 距离表全部设置为INTMAX 2 将起点的 换成表 和 距离表 设置为 0 3 将出发站信息存储到优先队列q中 { {0，0} ， {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结束- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
成果展示
代码实现
判断是最短路径还是最少换乘
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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
最短路径代码实现
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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
最少换乘代码实现
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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
根据所得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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
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(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
建立槽函数
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); });- 1
- 2
- 3
- 4
- 5
-
相关阅读:
最短路径问题
Godot VisualStudio外部编辑器设置
软件工程师必备书单
RedisConnectionException: Unable to connect to 127.0.0.1:6379
《计算机视觉中的多视图几何》笔记（1）
7.nodejs--egg框架简介、以及get、post请求
JDBC 在性能测试中的应用
【LeetCode每日一题:1684. 统计一致字符串的数目~~~字符串+遍历+模拟+计数】
如何做好医药产品说明书翻译？
线程池 的一些事
- 原文地址：https://blog.csdn.net/qq_52172364/article/details/133253681
