自贡市城市建设投资开发集团有限公司网站,2023最近的新闻大事,深圳市光明区实验学校,商标设计免费的app本算法全都基于广度优先 概念最短路径实现所用容器算法思路 最少换乘实现所需容器算法思路 成果展示代码实现判断是最短路径还是最少换乘最短路径代码实现最少换乘代码实现根据所得List画出线路 ui界面的维护#xff08;前提条件#xff09;界面初始化combox控件建立槽函数 概… 本算法全都基于广度优先 概念最短路径实现所用容器算法思路 最少换乘实现所需容器算法思路 成果展示代码实现判断是最短路径还是最少换乘最短路径代码实现最少换乘代码实现根据所得List画出线路 ui界面的维护前提条件界面初始化combox控件建立槽函数 概念 概念这里不过多介绍很多文章介绍 大体意思是队列思想每次入队相邻的节点按照队列以此调用 这里如果想要实现最短路最少换乘的话需要用到优先队列 在以上的基础上对队列进行dist距离的排序或者trans换乘次数的排序 每次去除最少的也类似于贪心 最短路径实现
所用容器
typedef std::pairint,int PII; //dist trans
typedef std::pairQString,QString nodea; //stationname linename
typedef std::pairPII,nodea PLL; //dist trans ..... ....
QMapQString,int dist; //距离表
QMapQString,int trans; //换乘
QMapnodea,bool final; //是否遍历过
QMapQString,nodeapre; //父节点维护
std::priority_queuePLL,std::vectorPLL , std::greaterPLL 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]我们需要判断换乘最少如果know.second 说明不需要换乘 我们判断trans[j.first] 是否大于 trans[now.first]即可 如果大于则更新如果know.second 说明需要换乘 我们判断trans[j.first] 是否大于 trans[now.first]1 即可 如果大于则更新7 最后等待while执行完毕 我们获得了 pre[ endstr ]的信息然后循环调用pre 直到00结束最少换乘实现
所需容器
QMapQString,int dist; //距离表QMapQString,int trans; //换乘QMapnodea,bool final; //是否遍历过typedef std::pairint,int PII; //换乘 距离typedef std::pairQString,QString nodea; //站点名 和 线路名typedef std::pairPII,nodea PLL; // 某个站点的换成次数 和 距离 以及父站点和所属线路QMapQString,nodeapre; //还原最少换乘的工具std::priority_queuePLL,std::vectorPLL , std::greaterPLL 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;}QMapQString, 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::pairint,int PII;
typedef std::pairQString,QString nodea;
typedef std::pairPII,nodea PLL;void getshortTimePath(QGraphicsView *graphicsView,const QString startstr,const QString endstr,QTextBrowser *textBrowser){qDebug()选择成功\n;const int IntMax INT32_MAX;QMapQString,int dist; //距离表QMapQString,int trans; //换乘QMapnodea,bool final; //是否遍历过for(auto i:Station.keys()){dist[i] IntMax;trans[i] IntMax;}QMapQString,nodeapre;pre[startstr] nodea{00,00};std::priority_queuePLL,std::vectorPLL , std::greaterPLL 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;QListnodeas;int t0;nodea u pre[endstr];while(u.second!00){s.append(u);qDebug()---u.first \n ;upre[u.first];t;if(t40) 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;QMapQString,int dist; //距离表QMapQString,int trans; //换乘QMapnodea,bool final; //是否遍历过for(auto i:Station.keys()){trans[i] IntMax;dist[i] IntMax;}QMapQString,nodeapre;pre[startstr] nodea{00,00};std::priority_queuePLL,std::vectorPLL , std::greaterPLL 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;QListnodeas;int t0;nodea u pre[endstr];while(u.second!00){s.append(u);qDebug()---u.first \n ;upre[u.first];t;if(t40) 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;QMapQString,int dist; //距离表QMapQString,int trans; //换乘QMapnodea,bool final; //是否遍历过for(auto i:Station.keys()){trans[i] IntMax;dist[i] IntMax;}QMapQString,nodeapre;pre[startstr] nodea{00,00};std::priority_queuePLL,std::vectorPLL , std::greaterPLL 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;QListnodeas;int t0;nodea u pre[endstr];while(u.second!00){s.append(u);qDebug()---u.first \n ;upre[u.first];t;if(t40) 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);});
