java地铁最短距离_地铁最短路径需求分析

主要功能

提供一副地铁线路图，计算指定两站之间最短(最少经过站数)乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：

地铁线路总数

线路名1 站名1 站名2 站名3 …

线路名2 站名1 站名2 站名3 …

线路名3 站名1 站名2 站名3 …..

1号线 苹果园 古城 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨路 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东

2号线 西直门 积水潭 鼓楼大街 安定门 雍和宫 东直门 东四十条 朝阳门 建国门 北京站 崇文门 前门 和平门 宣武门 长椿街 复兴门 阜成门 车公庄 西直门

4号线 大兴线 安河桥北 北宫门 西苑 圆明园 北京大学东门 中关村 海淀黄庄 人民大学 魏公村 国家图书馆 动物园 西直门 新街口 平安里 西四 灵境胡同 西单 宣武门 菜市口 陶然亭 北京南站 马家堡 角门西 公益西桥 新宫 西红门 高米店北 高米店南 枣园 清源路 黄村西大街 黄村火车站 义和庄 生物医药基地 天宫院

5号线 天通苑北 天通苑 天通苑南 立水桥 立水桥南 北苑路北 大屯东路 惠新四街北口 惠新四街南口 和平西桥 和平里北街 雍和宫 北新桥 张自忠路 东四 灯市口 东单 崇文门 磁器口 天坛东门 蒲黄榆 刘家窑 宋家庄

6号线 海淀五路居 慈寿寺 花园桥 白石桥南 车公庄西 车公庄 平安里 北海北 南锣鼓巷 东四 朝阳门 东大桥 呼家楼 金台路 十里堡 青年路 褡裢坡 黄渠 常营 草房 物资学院路 通州北关 北运河西 郝家府 东夏园 潞城

7号线 北京西站 湾子 达官营 广安门内 菜市口 虎坊桥 珠市口 桥湾 磁器口 广渠门内 广渠门外 九龙山 大郊亭 百子湾 化工 南楼梓庄 欢乐谷景区 双合 焦化厂

8号线 朱辛庄 育知路 平西府 回龙观东大街 霍营 育新 西小口 永泰庄 林萃桥 森林公园南门 奥林匹克公园 奥林中心 北土城 安华桥 安德里北街 鼓楼大街 什刹海 南锣鼓巷 中国美术馆

8号线南段 珠市口 天桥 永定门外 木樨园 海户屯 大红门南 和义 东高地 火箭万源 五福堂 德茂 瀛海

9号线 郭公庄 丰台科技园 科怡路 丰台南路 丰台东大街 七里庄 六里桥 六里桥东 北京西站 军事博物馆 白堆子 白石桥南 国家图书馆

10号线 巴沟 苏州街 海淀黄庄 知春里 知春路 西土城 牡丹园 健德门 北土城 安贞门 惠新西街南口 芍药居 太阳宫 三元桥 亮马桥 农业展览馆 团结湖 呼家楼 金台夕照 国贸 双井 劲松 潘家园 十里河 分钟寺 成寿寺 宋家庄 石榴庄 大红门 角门东 角门西 草桥 纪家庙 首经贸 丰台站 泥洼 西局 六里桥 莲花桥 公主坟 西钓鱼台 慈寿寺 车道沟 长春桥 火器营 巴沟

13号线 西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门

14号线东段 善各庄 来广营 东湖渠 望京 阜通 望京南 将台 东风北桥 枣营 朝阳公园 金台路 大望路 九龙山 平乐园 北工大西门 十里河 方庄 蒲黄榆 景泰 永定门外 北京南站

14号线西段 西局 七里庄 大井 郭庄子 大瓦窑 园博园 张郭庄

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

16号线 北安河 温阳路 稻香湖路 屯佃 永丰 永丰南 西北旺 马连洼 农大南路 西苑

八通线 四惠 四惠东 高碑店 传媒大学 双桥 管庄 八里桥 通州北苑 果园 九棵树 梨园 临河里 土桥

昌平线 昌平西山口 十三陵景区 昌平 昌平东关 北邵洼 南邵 沙河高教园 沙河 巩华城 朱辛庄 生命科学园 西二旗

房山线 阎村东 苏庄 良乡南关 良乡大学城西 良乡大学城 良乡大学城北 广阳城 篱笆房 长阳 稻田 大葆台 郭公庄

首都机场线 T3航站楼 T2航站楼 三元桥 东直门

西郊线 巴沟 颐和园西门 茶棚 万安 植物园 香山

燕房线 阎村东 紫草坞 阎村 星城 大石河东 马各庄 饶乐府 房山城关 燕山

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

需求分析

1.能够将地铁各个线路的站点导入

2.能够查询并输出每条线路的站点

3.能够计算并输出两个站点之间最短的乘车路线

实现语言

Java

实现算法

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止

类职责划分

Station类：定义了地铁站点的类结构和图结构以及一些方法

private String name; //站名

public Station before; //前一站

public Station next; //后一站

LineWithName类和LineNoName类：都是用来获取路线和总站点数，但LineNoName类不包含路线名

public static HashSet> lineSet = new HashSet>();　　//存放所有线的集合

public static int totalStaion = 0;　　//存放总站点数

Subway类：实现迪杰斯特拉算法，输出换乘路线

private List allPassed = new ArrayList();　　//存放读取过的站点的信息

String allStations = “”;　　//存放最短路径经过的站点名字

Main类：主函数，在命令框进行交互

核心代码

Station.java

//站点的类结构

public classStation {private String name;//站名

public Station before;//前一站

public Station next;//后一站//本站到某一目标站所经过的所有站的集合

private Map> orderSetMap = new HashMap>();public Map>getOrderSetMap() {returnorderSetMap;

}publicStation(String name) {this.name =name;

}publicString getName() {returnname;

}public voidsetName(String name) {this.name =name;

}//获取所有经过station的站点

public LinkedHashSetgetAllPassed(Station station) {if (orderSetMap.get(station) == null) {

LinkedHashSet set = new LinkedHashSet();

set.add(this);

orderSetMap.put(station, set);

}returnorderSetMap.get(station);

}}

LineWithName.java和LineNoName.java(总体结构相同，所以写在一起了，用注释标出)

//用来获取路线和总站点数

public classLineNoName {public static HashSet> lineSet = new HashSet>();//所有线的集合

public static int totalStaion = 0;//总站点数

public static void readFile(String file) throwsIOException{

FileReader fileReader= newFileReader(file);

BufferedReader bufferedReader= newBufferedReader(fileReader);

String str= null;while((str = bufferedReader.readLine()) != null)

{

List line = new ArrayList();

String[] lineInfor= str.split(” “);for(String s : lineInfor){

line.add(newStation(s));

}

line.remove(0);//去掉线路名(LineNoName)的语句

for(int i =0;i

line.get(i).next= line.get(i+1);

line.get(i+1).before =line.get(i);

}

}

lineSet.add(line);

totalStaion+=line.size();

}

fileReader.close();

bufferedReader.close();

}

}

Subway.java

//实现迪杰斯特拉算法，找到换乘路线

public classSubway {private List allPassedStation = new ArrayList();//放读取过的站点的信息

String Shortest = “”;//最短路径经过的站点名字

publicString Dijkstra(Station startStation, Station endStation) {//初始化起点站到某一站的集合

if(startStation.getOrderSetMap().isEmpty()) {

List Linkedstations =getAllLinked(startStation);for(Station s : Linkedstations) {

startStation.getAllPassed(s).add(s);

}

}//如果找完了全部的路径，则返回路线

if (allPassedStation.size() ==LineNoName.totalStaion) {

Shortest+=”一共经过” + (startStation.getAllPassed(endStation).size() – 1) + “站”+”\n”+”路线如下：”+”\n”;for(Station station : startStation.getAllPassed(endStation)) {

Shortest+=station.getName() + ” “;

}returnShortest;

}if (!allPassedStation.contains(startStation)) {

allPassedStation.add(startStation);

}

Station short1= getShortestPath(startStation);//获取距离起点站最近的一个站//如果找到的最近的站就是终点站，则返回路线

if (short1 ==endStation) {

Shortest+=”一共经过” + (startStation.getAllPassed(endStation).size() – 1) + “站”+”\n”+”路线如下：”+”\n”;for(Station station : startStation.getAllPassed(endStation)) {

Shortest+=station.getName() + ” “;

}returnShortest;

}//将现在的最短路线进行比较

for(Station short2 : getAllLinked(short1)) {//如果经过的站点里有最短路线,则跳出循环

if(allPassedStation.contains(short2)) {continue;

}int shortestPath = (startStation.getAllPassed(short1).size() – 1) + 1;//如果之前的最短路径里有该路线，比较出最短线路

if(startStation.getAllPassed(short2).contains(short2)) {//如果当前的最短路线比先前的短，则将最短路线改为现在的

if ((startStation.getAllPassed(short2).size() – 1) >shortestPath) {//重置最小路径

startStation.getAllPassed(short2).clear();

startStation.getAllPassed(short2).addAll(startStation.getAllPassed(short1));

startStation.getAllPassed(short2).add(short2);

}

}else{//如果之前的最短路线没有该路线，则加上该路线

startStation.getAllPassed(short2).addAll(startStation.getAllPassed(short1));

startStation.getAllPassed(short2).add(short2);

}

}

allPassedStation.add(short1);//循环直到符合判断条件

Dijkstra(startStation, endStation);returnShortest;

}}

Main.java

//主函数，在命令框进行交互

public classMain {public static void main(String[] args) throwsIOException {

Scanner input= newScanner(System.in);

String file= “D:\\Eclipse\\ruan\\station.txt”;

System.out.println(“请选择操作(输入对应数字即可)：1.查看全部路线。2.查询单条路线。3.查询两站最短路线。”);

String choose=input.nextLine();if(choose.equals(“1”)) {

Reader fr= null;int length = 0;char ch [] = null;try{

fr=newFileReader(file);

ch= new char[2048];

length=fr.read(ch);

System.out.println(new String(ch ,0,length));

}catch(FileNotFoundException e) {

e.printStackTrace();

}catch(IOException e) {

e.printStackTrace();

}finally{if(null!=fr){try{

fr.close();

}catch(IOException e) {

e.printStackTrace();

}

}

}

}else if (choose.equals(“2”)) {

System.out.println(“请输入路线名：”);

String lineName=input.nextLine();

LineWithName.readFile(file);

Station station= newStation(lineName);

String allStations= “”;int flag = 0;for (Listlinename : LineWithName.lineSet) {if(linename.contains(station)) {

allStations+=linename.get(0).getName() + “包括的站点:”+”\n”;for (int i = 1; i < linename.size(); i++) {

allStations+=linename.get(i).getName() + ” “;

}

flag=1;

}

}if(flag==0){

System.out.println(“—该路线不存在！—“);

}else{

System.out.println(allStations);

}

}else if (choose.equals(“3”)) {

System.out.println(“请输入起点：”);

String start=input.nextLine();

System.out.println(“请输入终点：”);

String end=input.nextLine();

LineNoName.readFile(file);

Station station1= newStation(start);

Station station2= newStation(end);int flag1 = 0,flag2 = 0;for (Listlinename : LineNoName.lineSet) {if(linename.contains(station1)) {

flag1=1;break;

}else{

flag1=0;

}

}for (Listlinename : LineNoName.lineSet) {if(linename.contains(station2)) {

flag2=1;break;

}else{

flag2=0;

}

}if(flag1==1&&flag2==1) {

Subway sw= newSubway();

String allStations= sw.Dijkstra(new Station(start), newStation(end));

System.out.println(allStations);

}else if (flag1==0&&flag2==1) {

System.out.println(“—没有该起点！—“);

}else if (flag1==1&&flag2==0) {

System.out.println(“—没有该终点！—“);

}else{

System.out.println(“—输入参数有误！—“);

}

}else{

System.out.println(“—输入参数有误！—“);

}

input.close();

}

}

测试用例

查看全部路线

查询单条路线

查询不存在或者错误的路线

查询两站最短路线

查询最短路线操作，输入不存在的终点、起点或两者都不存在

输入错误的操作

总结

第一次在博客园写博客，感觉还是很新奇的，如果觉得博客界面丑还请见谅，我也会学习一些好看的界面设计用法，争取一次界面比一次好看。

这次的作业对我而言还是蛮有难度的，花了很多时间去重新回顾学习之前学过的数据结构的迪杰斯特拉算法，以及一些Java类的用法，也参考学习了一些大佬写的算法，让我充分意识到了自己的不足之处，我还需要多练习来扎实自己代码的功底，这样才能更好的适应新的学习。

虽然实现了代码的基本功能，但还是有许多地方需要改进，这让我意识到好的需求分析对一个代码而言也很重要，只有设计好了思路，才能一步步的做下去。

附上github地址：https://github.com/lutaobaba/-/tree/master/%E5%9C%B0%E9%93%81%E6%9C%80%E7%9F%AD%E8%B7%AF%E7%BA%BF