北京地铁出行线路规划
参考
https://www.cnblogs.com/myp123/p/11669391.html
https://www.cnblogs.com/xupppp/p/11663525.html
项目介绍
规划
https://www.cnblogs.com/RittLiii/p/11570168.html
Github
https://github.com/RitaaaLxiii/subway
实现语言
java
主要算法
Dijkstra
类
| Main | 程序入口，进行输入操作，判断输入 |
| Station | model类，储存站点信息 |
| Routine | model类，储存地铁路线信息 |
| ReadSubwayMessage | 文件读取输出，实现subway.txt内容的提取，和查询内容文件输出 |
| Dijkstra | 算法实现最短路径 |
一、文件存储
将地铁线路站点存入subway.txt文件中
1号线 苹果园 古城 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨路 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东
2号线 积水潭 鼓楼大街 安定门 雍和宫 东直门 东四十条 朝阳门 建国门 北京站 崇文门 前门 和平门 宣武门 长椿街 复兴门 阜成门 车公庄 西直门 积水潭
4号线大兴线 安河桥北 北宫门 西苑 圆明园 北京大学东门 中关村 海淀黄庄 人民大学 魏公村 国家图书馆 动物园 西直门 新街口 平安里 西四 灵境胡同 西单 宣武门 菜市口 陶然亭 北京南站 马家堡 角门西 公益西桥 新宫 西红门 高米店北 高米店南 枣园 清源路 黄村西大街 黄村火车站 义和庄 生物医药基地 天宫院
...
二、核心代码
Model
Station.java
存储站点信息
public class Station { private String name; //站点名 private String lineName;//站点路线名 private List<Station> nearStation = new ArrayList<Station>(); //邻接站点 ... public Station(String name, String lineName) { this.name = name; this.lineName = lineName; } ...省略set&get }
Routine.java
存储路线信息
public class Routine { private Station starStation;//初始站 private Station endStation;//目的站 private int distance;//距离 private Station preStations; //前一个站点 ... public Routine(Station starStation, Station endStation, int distance) { this.starStation = starStation; this.endStation = endStation; this.distance = distance; } ... }
文件的读取与输出
创建lines存储从subway.txt提取出的地铁线路站点信息，创建lineMap存储当前最短路径
public static LinkedHashSet<List<Station>> lines = new LinkedHashSet<List<Station>>();//地铁线路信息 public static HashMap<String, List<Station>> lineMap = new HashMap<>();//地铁线路集合
提取subway.txt
public static void readFile() { File file = new File(fileIn);//创建新file存储输入文件 BufferedReader reader = null; try { InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(file), "UTF-8"); reader = new BufferedReader(inputStreamReader); String line = null; while ((line = reader.readLine()) != null) {//依次读取txt每一行 List<Station> list = new ArrayList<Station>();//创建数组存储线路站点信息 String[] lineStationList = line.trim().split(" ");//.trim 除去每行左右空格；.split(" ") 当碰到“ ”时，将前面内容存入数组 String lineStationName = lineStationList[1];//lineStationName等于每行线路名 for(int i =2;i<lineStationList.length;i++) { Station station = new Station(lineStationList[i],lineStationName);//将站点信息封装传递给station list.add(station);//list存储当前线路的站点信息 } lines.add(list);//将每行站点信息传给lines } } catch (IOException e) { e.printStackTrace(); } }
Dijkstra
本次实验地铁不用考虑每个站点之间的距离大小，所以将每两站间距离设为1。将输入站作为初始点，通过遍历lins查找其相邻站点，将相邻站点保存。先将后一位先放入resultMap存储最短路线，对距离进行比较，若新路径小于存储的最短路径，则替代。
当该站点与下一站点不在同一线路上，换乘。
private static List<Station> visitedList = new ArrayList<>(); //存储已经过的站点 private static HashMap<Station, Routine> resultMap = new HashMap<>(); //存储当前最短路线
最短路径
public static Routine shortDistance(Station start,Station end) { if(!visitedList.contains(start)) {//当经过的站点没有输入的初始站，将初始站加入 visitedList.add(start); } if(resultMap.isEmpty()) {//如果当前最短路线为空 List<Station> station = getNearStation(start);//查询输入站周围站点 // 将相邻站点加入结果集 for (Station station1 : station) { Routine routine = new Routine(); routine.setStarStation(start); routine.setEndStation(end); routine.setDistance(1);//默认站点间距离都为1 routine.getPassedStations().add(station1); resultMap.put(station1, routine); } } Station next = getNextStation();//获取下一个站点 if (next == null) { //当下个站点为空时，初始化 Routine path = new Routine(); path.setDistance(0); path.setStarStation(start); path.setEndStation(end); return resultMap.put(end, path); } if (next.equals(end)) {//如果下一个站点就是终点站，直接输出 return resultMap.get(next); } //查询下一站点所有相邻站点 List<Station> NLinkStation = getNearStation(next); for (Station N : NLinkStation) {//遍历下一站点所有相邻站点 if (visitedList.contains(N)) {//如果经过的站点中包含该站点，继续 continue; } int distance = 0;//定义距离为0 if (next.getName().equals(N.getName())) {//如果下一站点和遍历相同，距离不变 distance = 0; } int NDistance = resultMap.get(next).getDistance(); distance = NDistance + 1; List<Station> PrePassStation = resultMap.get(next).getPassedStations(); Routine NResult = resultMap.get(N); if (NResult != null) { // 含有最佳相邻点 if (NResult.getDistance() > distance) {//如果存储值大于distance，distance替代 NResult.setDistance(distance); NResult.getPassedStations().clear(); NResult.getPassedStations().addAll(PrePassStation); NResult.getPassedStations().add(N); } } else { NResult = new Routine(); // 没有最佳相邻点 NResult.setDistance(distance); NResult.setStarStation(start); NResult.setEndStation(N); NResult.getPassedStations().addAll(PrePassStation); NResult.getPassedStations().add(N); } resultMap.put(N, NResult); } visitedList.add(next); return shortDistance(start, end); }
获取相邻站点信息
public static List<Station> getNearStation(Station station){ List<Station> nearStation = new ArrayList<Station>(); for(List<Station> line:ReadSubwayMessage.lines) {//遍历lines for(int i = 0;i<line.size();i++) { if(station.equals(line.get(i))) {//如果输入的站点和lines中相等 if(i==0) {//当i==0时，即此站点为起始站，相邻站只有后面一站输入,将后一站放入 nearStation.add(line.get(i+1)); } else if(i==(line.size())-1) {//如果i==（line.size()）-1,则此站点是末站，相邻站只有前面一站 nearStation.add(line.get(i - 1)); } else {//位于始末中间的位置，相邻站为前后 nearStation.add(line.get(i + 1)); nearStation.add(line.get(i - 1)); } } } } return nearStation; }
获取下一站点信息
private static Station getNextStation() { Station station = null; int min = 10000; Set<Station> stations = resultMap.keySet();//stations存resultMap当前 for(Station station1 : stations) { if(visitedList.contains(station1)) { continue; } Routine routine = resultMap.get(station1); if(routine.getDistance()<min) { min = routine.getDistance(); station = routine.getEndStation(); } } return station; }
Main
通过判断输入args[]信息，做出相应输出。“-map”输出subway.txt文件内容，“-a”输出相应地铁线路所有站点，“-b”输出两站间最短路径。
public static void main(String[] args) throws IOException{ switch(args[0]) { case "-map": //java Main -map subway.txt //输出subway.txt内容 if(args.length==2) { ReadSubwayMessage.fileIn = System.getProperty("user.dir")+File.separator+"\\"+args[1]; ReadSubwayMessage.readFile(); System.out.println("输入正确"); } else { System.out.println("输入错误"); break; } break; case "-a"://java Main -a 1号线 -map subway.txt -o routine.txt //查询地铁线路 if(args.length==6) { ReadSubwayMessage.fileIn = System.getProperty("user.dir")+File.separator+"\\"+args[3]; ReadSubwayMessage.fileOut = System.getProperty("user.dir")+File.separator+"\\"+args[5]; ReadSubwayMessage.readFile(); ReadSubwayMessage.writeLine(args[1]); ReadSubwayMessage line = new ReadSubwayMessage(); line.readLine(); } else { System.out.println("输入错误"); break; } break; case "-b"://java Main -b 万松路 中关村 -map subway.txt -o routine.txt //查询最短路线 if(args.length==7) { ReadSubwayMessage.fileIn = System.getProperty("user.dir")+File.separator+"\\"+args[4]; ReadSubwayMessage.fileOut = System.getProperty("user.dir")+File.separator+"\\"+args[6]; ReadSubwayMessage.readFile(); Routine path = Dijkstra.shortDistance(new Station(args[1]), new Station(args[2])); ReadSubwayMessage.writeShortestLine(path); System.out.println("路线：:"); Routine line = new Routine(); path.readShort(); } else { System.out.println("输入错误"); break; } break; default: System.out.println("输入错误"); } }
三、测试
1. -map subway.txt
2. -a 1号线 -map subway.txt -o routine.txt
3. -b 万松路 中关村 -map subway.txt -o routine.txt
四、个人小结
本次实验过程不是很顺利，暴露出很多自身的问题。自己的基础知识不够充足，一时无法纯靠自己写出完整代码，最后参考了许多博客，问了不同的人对此问题的解题思路，才得以写完，但还是在文件读取、输出上有着问题。这次个人实验让我再次巩固了数据结构，熟练dijkstra算法，并对java的map，HashMap用法更加熟练。
从今天起认真复习基础知识，努力学习新的知识，充实自我，希望在团队项目中更好的奉献。
版权声明：本文为RittLiii原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。