天坛东门

地铁线路最短路径

1.主要功能

地铁线路图

  以北京地铁为例，地铁线路信息保存在中，格式如下：

1号线

苹果园古城⼋⾓游乐园⼋宝⼭⽟泉路五棵松万寿路公主坟军事博物馆⽊樨路南礼⼠路复兴门西单天安门西天安门东王府井东单建国

门永安⾥国贸⼤望路四惠四惠东

2号线

西直门积⽔潭⿎楼⼤街安定门雍和宫东直门东四⼗条朝阳门建国门北京站崇⽂门前门和平门宣武门长椿街复兴门⾩成门车公庄西

直门

4号线

⼤兴线安河桥北北宫门西苑圆明园北京⼤学东门中关村海淀黄庄⼈民⼤学魏公村国家图书馆动物园西直门新街⼝平安⾥西四灵境胡

同西单宣武门菜市⼝陶然亭北京南站马家堡⾓门西公益西桥新宫西红门⾼⽶店北⾼⽶店南枣园清源路黄村西⼤街黄村⽕车站义和庄

⽣物医药基地天宫院

5号线

天通苑北天通苑天通苑南⽴⽔桥⽴⽔桥南北苑路北⼤屯东路惠新四街北⼝惠新四街南⼝和平西桥和平⾥北街雍和宫北新桥张⾃忠路

东四灯市⼝东单崇⽂门磁器⼝天坛东门蒲黄榆刘家窑宋家庄

6号线

海淀五路居慈寿寺花园桥⽩⽯桥南车公庄西车公庄平安⾥北海北南锣⿎巷东四朝阳门东⼤桥呼家楼⾦台路⼗⾥堡青年路褡裢坡黄渠

常营草房物资学院路通州北关北运河西郝家府东夏园潞城

7号线

北京西站湾⼦达官营⼴安门内菜市⼝虎坊桥珠市⼝桥湾磁器⼝⼴渠门内⼴渠门外九龙⼭⼤郊亭百⼦湾化⼯南楼梓庄欢乐⾕景区双合

焦化⼚

8号线

朱⾟庄育知路平西府回龙观东⼤街霍营育新西⼩⼝永泰庄林萃桥森林公园南门奥林匹克公园奥林中⼼北⼟城安华桥安德⾥北街⿎楼

⼤街什刹海南锣⿎巷中国美术馆

8号线南段

珠市⼝天桥永定门外⽊樨园海户屯⼤红门南和义东⾼地⽕箭万源五福堂德茂瀛海

9号线

郭公庄丰台科技园科怡路丰台南路丰台东⼤街七⾥庄六⾥桥六⾥桥东北京西站军事博物馆⽩堆⼦⽩⽯桥南国家图书馆

10号线

巴沟苏州街海淀黄庄知春⾥知春路西⼟城牡丹园健德门北⼟城安贞门惠新西街南⼝芍药居太阳宫三元桥亮马桥农业展览馆团结湖呼

家楼⾦台⼣照国贸双井劲松潘家园⼗⾥河分钟寺成寿寺宋家庄⽯榴庄⼤红门⾓门东⾓门西草桥纪家庙⾸经贸丰台站泥洼西局六⾥

桥莲花桥公主坟西钓鱼台慈寿寺车道沟长春桥⽕器营巴沟

13号线

西直门⼤钟寺知春路五道⼝上地西⼆旗龙泽回龙观霍营⽴⽔桥北苑望京西芍药居光熙门柳芳东直门

14号线东段

善各庄来⼴营东湖渠望京⾩通望京南将台东风北桥枣营朝阳公园⾦台路⼤望路九龙⼭平乐园北⼯⼤西门⼗⾥河⽅庄蒲黄榆景泰永

定门外北京南站

14号线西段

西局七⾥庄⼤井郭庄⼦⼤⽡窑园博园张郭庄

15号线

俸伯顺义⽯门南法信后沙峪花梨坎国展孙河马泉营崔各庄望京东望京望京西关庄⼤屯路东安⽴路奥林匹克公园北沙滩六道⼝清华

东路西⼝

16号线

北安河温阳路稻⾹湖路屯佃永丰永丰南西北旺马连洼农⼤南路西苑

⼋通线

四惠四惠东⾼碑店传媒⼤学双桥管庄⼋⾥桥通州北苑果园九棵树梨园临河⾥⼟桥

昌平线

昌平西⼭⼝⼗三陵景区昌平昌平东关北邵洼南邵沙河⾼教园沙河巩华城朱⾟庄⽣命科学园西⼆旗

房⼭线

阎村东苏庄良乡南关良乡⼤学城西良乡⼤学城良乡⼤学城北⼴阳城篱笆房长阳稻⽥⼤葆台郭公庄

⾸都机场线

T3航站楼T2航站楼三元桥东直门

西郊线

巴沟颐和园西门茶棚万安植物园⾹⼭

燕房线

阎村东紫草坞阎村星城⼤⽯河东马各庄饶乐府房⼭城关燕⼭

亦庄线

宋家庄肖村⼩红门旧宫亦庄桥亦庄⽂化园万源街荣京东街荣昌东街同济南路经海路次渠南次渠亦庄⽕车站

提供⼀副地铁线路图，计算指定两站之间最短（最少经过站数）乘车路线；输出指定地铁线路的所有站点。

2.实现语⾔

编程语⾔：

  Java语⾔

IDE：

  Eclip

3.实现算法

BFS算法（⼴度优先算法）BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中⽌。⼴度优先搜索的实现

⼀般采⽤open-clod表。

4、类职责划分

类

⽤来保存地铁线路的属性

privateStringname;

privateArrayListroute=newArrayList<>();//存放线路的站点

n类

⽤于保存地铁站点的属性

privateStationps;//前⼀站点

privateintdistance;//距离

privateintturnNum=0;//换乘

privateintisVisted=0;//是否已经访问

privateArrayListsor=newArrayList<>();//stationofroute站点所在线路名（可能存在多条线路有该站）

privateArrayListsb=newArrayList<>();//stationbeside接邻站

p类

ArrayListroute=newArrayList<>();

publicloadMap(Stringpath)throwsIOException

2类

主程序

5、核⼼代码

加载读⼊txt中的信息并存储

BufferedReaderbr=newBufferedReader(newInputStreamReader(newFileInputStream(newFile(path)),"UTF-8"));

//读⼊txt⽂件

try{

Stringin=null;//读⼊字符串

while((in=ne())!=null){

Router=newRoute();

String[]s=("");//分隔每⾏的每个线路名和站点

e(s[0]);//每⾏第⼀个是线路名

for(inti=1;i<;i++){

tion(s[i]);//除第⼀个都是站点名

}

(r);

}

对环线的⾸尾站点进⾏读⼊属性

Stations=newStation();

e((0));//站点

(routeName);//所在线路

((1));//读⼊接邻站

((()-2));

(s);

对⽆环线的⾸尾站点进⾏读⼊

⾸

Stations=newStation();

e((0));//站点

(routeName);//所在线路

((1));

(s);

尾

Stations=newStation();

e((()-1));//站点

(routeName);//所在线路

((()-2));

(s);

其余站点

for(intm=1;m<()-1;m++){

isin=0;

for(intn=0;n<();n++){

//遍历

if((n).getName().equals((m))){

isin=1;

(n).tSor(routeName);

(n).tSb((m-1));

(n).tSb((m+1));

break;

}

}

if(isin==0){

Stations=newStation();

e((m));

(routeName);

//前后站点邻站

((m-1));

((m+1));

(s);

}

}

BFS算法

Queuequeue=newLinkedList<>();//链表模拟队列

(fsIndex).tIsVisited(1);//标记访问

((fsIndex));//初始站点⼊队列

intdistance=0;//保存步数

while(!y()){

StationtopS=();//移出队列头部

if(distance==0){//判断是不是队头

tance(distance);//存⼊步数

distance++;

}el{

//判断是否换乘

distance=().getDistance();

tance(distance+1);

distance++;

}

(topS);//结果集增加

ArrayListtmpSb=(station);

for(inti=0;i<();i++){

if((i).getIsVisited()==0){//判断是否访问过

(i).tPs(topS);//保存前置站点为当前站点

(i).tIsVisited(1);//标记访问

((i));//若未访问过则直接存⼊队列

}

}

}

sta=result;

//找终点站

intendIndex=-1;

inti=0;

while(i<()){

Stationtmp=(i);

if(e().equals(endStation)){

endIndex=i;

break;

}i++;

}

//若未找到则报错结束

if(endIndex==-1){

n("未找到该终点站");

(0);

}

Stackstack=newStack<>();

//建⽴栈以实现逆序输出

Stationtmp=(endIndex);//栈底为终点站

if(tance()==0){

n("该站为始发站");

}

distance=tance();//⽤于保存途经站点数

inttransNum=0;//⽤于保存换乘数

//逐步⼊栈

while(()!=null){

(tmp);

tmp=();//更新为前置站点⼊栈

}

//判断换乘

ArrayListr1=();

ArrayListr2=().getSor();

Stringnow="";//⽤于保存当前线路

intflag=0;

//寻找当前线路

i=0;

while(i<()){

for(intj=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(intj=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++;

}el{

tmp=();

("-->"+().getName());

}

}

Main

Scannerinput=newScanner();

//读取⽂件

loadMaplm=newloadMap("C:");

//提取所保存的站点和线路信息

ArrayListstation=tion();

ArrayListroute=te();

//输出所有线路名称

for(inti=0;i<();i++){

((i).getName()+"");

}

n();

//输出菜单

n("请选择:n1.查询线路2.搜索最短路线");

//输⼊

intchoo=t();

switch(choo){

ca1:{

("请输⼊查询的线路名:");

Stringname=();

intindex=-1;

inti=0;

while(i<()){

if((i).getName().equals(name)){

index=i;

break;

}

i++;

}

if(index==-1){

n("该线路名不存在");

}el{

n((index).getName()+":"+(index).showRoute());

}

}

ca2:{

BFS2bfs=newBFS2();

("请输⼊始发站:");

Stringstart=();

("请输⼊终点站:");

Stringend=();

th(start,end,station);

}

}

}

6、测试⽤例

查询并且⽆换乘乘坐

查询失败

站名不存在

多次换乘测试

7、总结

学会了写博客，还有加强了java编程能⼒，更详细地学习并运⽤了算法。