2023年7月4日发(作者：)

地铁线路最短路径1.主要功能地铁线路图  以北京地铁为例，地铁线路信息保存在中，格式如下：1号线苹果园 古城 ⼋⾓游乐园 ⼋宝⼭ ⽟泉路 五棵松 万寿路 公主坟 军事博物馆 ⽊樨路 南礼⼠路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安⾥ 国贸 ⼤望路 四惠 四惠东2号线西直门 积⽔潭 ⿎楼⼤街 安定门 雍和宫 东直门 东四⼗条 朝阳门 建国门 北京站 崇⽂门 前门 和平门 宣武门 长椿街 复兴门 ⾩成门 车公庄 西直门4号线⼤兴线 安河桥北 北宫门 西苑 圆明园 北京⼤学东门 中关村 海淀黄庄 ⼈民⼤学 魏公村 国家图书馆 动物园 西直门 新街⼝ 平安⾥ 西四 灵境胡同 西单 宣武门 菜市⼝ 陶然亭 北京南站 马家堡 ⾓门西 公益西桥 新宫 西红门 ⾼⽶店北 ⾼⽶店南 枣园 清源路 黄村西⼤街 黄村⽕车站 义和庄⽣物医药基地 天宫院5号线天通苑北 天通苑 天通苑南 ⽴⽔桥 ⽴⽔桥南 北苑路北 ⼤屯东路 惠新四街北⼝ 惠新四街南⼝ 和平西桥 和平⾥北街 雍和宫 北新桥 张⾃忠路东四 灯市⼝ 东单 崇⽂门 磁器⼝ 天坛东门 蒲黄榆 刘家窑 宋家庄6号线海淀五路居 慈寿寺 花园桥 ⽩⽯桥南 车公庄西 车公庄 平安⾥ 北海北 南锣⿎巷 东四 朝阳门 东⼤桥 呼家楼 ⾦台路 ⼗⾥堡 青年路 褡裢坡 黄渠常营 草房 物资学院路 通州北关 北运河西 郝家府 东夏园 潞城7号线北京西站 湾⼦ 达官营 ⼴安门内 菜市⼝ 虎坊桥 珠市⼝ 桥湾 磁器⼝ ⼴渠门内 ⼴渠门外 九龙⼭ ⼤郊亭 百⼦湾 化⼯ 南楼梓庄 欢乐⾕景区 双合焦化⼚8号线朱⾟庄 育知路 平西府 回龙观东⼤街 霍营 育新 西⼩⼝ 永泰庄 林萃桥 森林公园南门 奥林匹克公园 奥林中⼼ 北⼟城 安华桥 安德⾥北街 ⿎楼⼤街 什刹海 南锣⿎巷 中国美术馆8号线南段珠市⼝ 天桥 永定门外 ⽊樨园 海户屯 ⼤红门南 和义 东⾼地 ⽕箭万源 五福堂 德茂 瀛海9号线郭公庄 丰台科技园 科怡路 丰台南路 丰台东⼤街 七⾥庄 六⾥桥 六⾥桥东 北京西站 军事博物馆 ⽩堆⼦ ⽩⽯桥南 国家图书馆10号线巴沟 苏州街 海淀黄庄 知春⾥ 知春路 西⼟城 牡丹园 健德门 北⼟城 安贞门 惠新西街南⼝ 芍药居 太阳宫 三元桥 亮马桥 农业展览馆 团结湖 呼家楼 ⾦台⼣照 国贸 双井 劲松 潘家园 ⼗⾥河 分钟寺 成寿寺 宋家庄 ⽯榴庄 ⼤红门 ⾓门东 ⾓门西 草桥 纪家庙 ⾸经贸 丰台站 泥洼 西局 六⾥桥 莲花桥 公主坟 西钓鱼台 慈寿寺 车道沟 长春桥 ⽕器营 巴沟13号线西直门 ⼤钟寺 知春路 五道⼝ 上地 西⼆旗 龙泽 回龙观 霍营 ⽴⽔桥 北苑 望京西 芍药居 光熙门 柳芳 东直门14号线东段善各庄 来⼴营 东湖渠 望京 ⾩通 望京南 将台 东风北桥 枣营 朝阳公园 ⾦台路 ⼤望路 九龙⼭ 平乐园 北⼯⼤西门 ⼗⾥河 ⽅庄 蒲黄榆 景泰 永定门外 北京南站14号线西段西局 七⾥庄 ⼤井 郭庄⼦ ⼤⽡窑 园博园 张郭庄15号线俸伯 顺义 ⽯门 南法信 后沙峪 花梨坎 国展 孙河 马泉营 崔各庄 望京东 望京 望京西 关庄 ⼤屯路东 安⽴路 奥林匹克公园 北沙滩 六道⼝ 清华东路西⼝16号线北安河 温阳路 稻⾹湖路 屯佃 永丰 永丰南 西北旺 马连洼 农⼤南路 西苑⼋通线四惠 四惠东 ⾼碑店 传媒⼤学 双桥 管庄 ⼋⾥桥 通州北苑 果园 九棵树 梨园 临河⾥ ⼟桥昌平线昌平西⼭⼝ ⼗三陵景区 昌平 昌平东关 北邵洼 南邵 沙河⾼教园 沙河 巩华城 朱⾟庄 ⽣命科学园 西⼆旗房⼭线阎村东 苏庄 良乡南关 良乡⼤学城西 良乡⼤学城 良乡⼤学城北 ⼴阳城 篱笆房 长阳 稻⽥ ⼤葆台 郭公庄⾸都机场线T3航站楼 T2航站楼 三元桥 东直门西郊线巴沟 颐和园西门 茶棚 万安 植物园 ⾹⼭燕房线阎村东 紫草坞 阎村 星城 ⼤⽯河东 马各庄 饶乐府 房⼭城关 燕⼭亦庄线宋家庄 肖村 ⼩红门 旧宫 亦庄桥 亦庄⽂化园 万源街 荣京东街 荣昌东街 同济南路 经海路 次渠南 次渠 亦庄⽕车站提供⼀副地铁线路图，计算指定两站之间最短（最少经过站数）乘车路线；输出指定地铁线路的所有站点。2.实现语⾔编程语⾔：  Java语⾔IDE：  Eclipse3.实现算法BFS算法（⼴度优先算法）BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中⽌。⼴度优先搜索的实现⼀般采⽤open-closed表。4、类职责划分类⽤来保存地铁线路的属性 private String name; private ArrayList route=new ArrayList<>();//存放线路的站点n类⽤于保存地铁站点的属性 private Station ps;//前⼀站点 private int distance;//距离 private int turnNum=0;//换乘 private int isVisted=0;//是否已经访问 private ArrayList sor= new ArrayList<>();//station of route站点所在线路名（可能存在多条线路有该站） private ArrayList sb= new ArrayList<>();//station beside 接邻站p类 ArrayList route= new ArrayList<>(); public loadMap(String path) throws 2类主程序5、核⼼代码加载读⼊txt中的信息并存储BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(path)), "UTF-8")); //读⼊txt⽂件 try {

String in=null;//读⼊字符串 while((in = ne())!=null) { Route r = new Route(); String[] s=(" ");//分隔每⾏的每个线路名和站点 e(s[0]);//每⾏第⼀个是线路名 for(int i=1;i<;i++) { tion(s[i]);//除第⼀个都是站点名

}

(r); }对环线的⾸尾站点进⾏读⼊属性 Station s=new Station(); e((0));//站点 (routeName);//所在线路 ((1));//读⼊接邻站 ((()-2)); (s);

对⽆环线的⾸尾站点进⾏读⼊⾸ Station s=new Station(); e((0));//站点 (routeName);//所在线路 ((1)); (s);尾 Station s=new Station(); e((()-1));//站点 (routeName);//所在线路 ((()-2)); (s);其余站点 for(int m=1;m<()-1;m++) { isin=0; for(int n=0;n<();n++) { //遍历 if((n).getName().equals((m))) { isin=1; (n).setSor(routeName); (n).setSb((m-1)); (n).setSb((m+1)); break; } } if(isin==0) { Station s = new Station(); e((m)); (routeName); //前后站点邻站 ((m-1)); ((m+1)); (s); } }BFS算法 Queue queue = new LinkedList<>();//链表模拟队列 (fsIndex).setIsVisited(1);//标记访问 ((fsIndex));//初始站点⼊队列

int distance=0;//保存步数 while(!y()) { Station topS = ();//移出队列头部

if(distance==0) {//判断是不是队头 tance(distance);//存⼊步数 distance++; }else { //判断是否换乘 distance=().getDistance(); tance(distance+1); distance++; } (topS);//结果集增加

ArrayList tmpSb = (station); for(int i=0;i<();i++) { if((i).getIsVisited()==0) {//判断是否访问过 (i).setPs(topS);//保存前置站点为当前站点 (i).setIsVisited(1);//标记访问 ((i));//若未访问过则直接存⼊队列 } }

} sta= result; //找终点站 int endIndex=-1; int i=0; while(i<()) { Station tmp = (i); if(e().equals(endStation)) { endIndex=i; break; }i++; } //若未找到则报错结束 if(endIndex==-1) { n("未找到该终点站"); (0); }

Stack stack = new Stack<>(); //建⽴栈以实现逆序输出 Station tmp = (endIndex);//栈底为终点站 if(tance()==0) { n("该站为始发站"); } distance = tance();//⽤于保存途经站点数 int transNum = 0;//⽤于保存换乘数 //逐步⼊栈 while(()!=null) { (tmp); tmp=();//更新为前置站点⼊栈 }

//判断换乘 ArrayList r1 =(); ArrayList r2 = ().getSor(); String now="";//⽤于保存当前线路 int flag=0; //寻找当前线路 i=0; while(i<()) { for(int j=0;j<();j++) { if((i).equals((j))) { now=(i); flag=1; break; } } if(flag==1) { break; }i++; } n("起始为："+now); (e()); //出栈 while(!y()) { //判断是否换乘 r1 = (); r2 = ().getSor(); flag=0; for(i=0;i<();i++) { for(int j=0;j<();j++) { //若两个站点所共有的线路与当前线路不同，则为换乘线路 if((i).equals((j))&&(!((i)))) { now=(i); flag=1; break; } } if(flag==1) { break; } } if(flag==1) { tmp=(); n(); n("换乘⾄："+now); (().getName()); transNum++; }else { tmp=(); ("-->"+().getName()); }

}

Main Scanner input = new Scanner();

//读取⽂件 loadMap lm=new loadMap("C:"); //提取所保存的站点和线路信息 ArrayList station= tion(); ArrayList route= te(); //输出所有线路名称 for(int i=0;i<();i++) { ((i).getName()+" "); } n(); //输出菜单 n("请选择: n1.查询线路 2.搜索最短路线"); //输⼊ int choose = t(); switch(choose) { case 1:{ ("请输⼊查询的线路名: "); String name = (); int index=-1; int i=0; while(i<()) { if((i).getName().equals(name)) { index=i; break; } i++; } if(index==-1) { n("该线路名不存在"); }else { n((index).getName()+":"+(index).showRoute()); } } case 2:{ BFS2 bfs = new BFS2(); ("请输⼊始发站: "); String start = (); ("请输⼊终点站: "); String end = (); th(start,end, station); } } }6、测试⽤例查询并且⽆换乘乘坐查询失败站名不存在多次换乘测试7、总结学会了写博客，还有加强了java编程能⼒，更详细地学习并运⽤了算法。