本算法全都基于广度优先
- 概念
- 最短路径实现
- 所用容器
- 算法思路
- 最少换乘实现
- 所需容器
- 算法思路
- 成果展示
- 代码实现
- 判断是最短路径还是最少换乘
- 最短路径代码实现
- 最少换乘代码实现
- 根据所得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中 { {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结束
最少换乘实现
所需容器
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中 { {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结束
成果展示
代码实现
判断是最短路径还是最少换乘
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);});