个人项目——地铁最短路径
项目介绍
主要功能
提供一副地铁线路图，计算指定两站之间最短（最少经过站数）乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：
地铁线路总数
线路名1站名1站名2站名3...
线路名2站名1站名2站名3...
线路名3站名1站名2站名3......
1、问题需求
- 程序能正确处理输入的命令行、
- 程序能正确输出指定地铁线经过的站点
- 程序能正确输出两个站点间的最短路径
2、实现语言
java
3、实现算法
Dijkstra
4、类职责划分
| Station.java | 储存站信息 |
| Subway.java | Main函数 |
|
MyMap.java |
储存map信息 |
| Line.java | 储存线路信息 |
5、核心代码
- 读入txt
public static void readText(String fileName) throws IOException {
File file = new File(fileName);
InputStreamReader reader = new InputStreamReader(
new FileInputStream(file));
BufferedReader br = new BufferedReader(reader);
String content = null;
content = br.readLine();
while (content != null) {
String[] contents=content.split(",");
Line line = new Line();
line.setLineName(contents[0]);
Station station = null;
for (int i = 1; i < contents.length; i++) {
if(!MyMap.stationMap.containsKey(contents[i])) {
station = new Station();
station.setStationName(contents[i]);
}
station = MyMap.myMap.getStation(contents[i]);
station.setLine(line);
line.addStation(station);
if(i!=1) {
station.addPreStation(line.getStation(i-2));
line.getStation(i-2).addPostStation(station);
}
else {
station.addPreStation(null);
}
if(i==contents.length-1) {
station.addPostStation(null);
}
}
content = br.readLine(); // 一次读入一行数据
}
br.close();
}
- 输出线路的站点信息
public static void printStationList(String lineName, String fileName) throws IOException {
File writename = new File(fileName); // 相对路径
writename.createNewFile(); // 创建新文件
BufferedWriter out = new BufferedWriter(new FileWriter(writename));
Line line = MyMap.myMap.getLine(lineName);
System.out.println(lineName+":");
out.write(lineName+"\r\n"); // \r\n为换行
out.flush(); // 把缓存区内容压入文件
for (Station station : line.getStationList()) {
System.out.println(station.getStationName());
out.write(station.getStationName()+"\r\n"); // \r\n为换行
out.flush(); // 把缓存区内容压入文件
}
out.close();
}
- 输出最短路径
public static void printShortestLine(String startStation, String endStation, String fileName) throws IOException {
File writename = new File(fileName); // 相对路径
writename.createNewFile(); // 创建新文件
BufferedWriter out = new BufferedWriter(new FileWriter(writename));
Station start = MyMap.myMap.getStation(startStation);
Station end = MyMap.myMap.getStation(endStation);
bfs(start,end);
Stack<Station> stationStack = new Stack<Station>();
Stack<Line> lineStack = new Stack<Line>();
Station cur=end;
while(cur!=null) {
stationStack.push(cur);
List<Line> line = new ArrayList<Line>();
line.addAll(cur.getLineList());//list拷贝
//System.out.println(cur.getStationName());
//System.out.println(cur.getParent().getStationName());
cur = cur.getParent();
if(cur==null)
break;
line.retainAll(cur.getLineList());//取交集
lineStack.push(line.get(0));//默认交集只有一个
}
Line preLine = lineStack.peek();
Line curLine = null;
while(!stationStack.isEmpty()) {
Station station = stationStack.pop();
out.write(station.getStationName()+" "); // \r\n为换行
out.flush(); // 把缓存区内容压入文件
System.out.print(station.getStationName());
if(!lineStack.empty()) {
curLine = lineStack.pop();
if(curLine!=preLine) {
System.out.print(curLine.getLineName());
out.write(curLine.getLineName()); // \r\n为换行
out.flush(); // 把缓存区内容压入文件
}
preLine = curLine;
}
out.write("\r\n"); // \r\n为换行
out.flush(); // 把缓存区内容压入文件
System.out.print("\n");
}
out.close();
}
- Station类
private String stationName;
private List<Line> lineList;
private List<Station> preStation;
private List<Station> postStation;
private Station parent;
- Line类
private String lineName;
private List<Station> stationList;
- MyMap类
public static MyMap myMap = new MyMap();
public static java.util.Map<String, Line> lineMap;
public static java.util.Map<String, Station> stationMap;
- bfs广度优先搜索
public static void bfs(Station start, Station end) {
Queue<Station> queue = new LinkedList<Station>();
queue.add(start);
while(!queue.isEmpty()) {
Station cur = queue.poll();
MyMap.myMap.visited(cur);
if(cur == end)
break;
List<Station> list = new ArrayList<Station>();
list.addAll(cur.getPreStation());
list.addAll(cur.getPostStation());
for(Station station : list) {
if(station!=null&&!MyMap.myMap.isVisited(station)) {
station.setParent(cur);
queue.add(station);
}
}
}
}
6、测试用例
- 一条线路起始到另外一条线路终点
-b 香山 焦化厂 -map 地铁线路信息.txt -o shortest.txt
香山 植物园 万安 茶棚 颐和园西门 巴沟10号线 苏州街 海淀黄庄4号线大兴线 人民大学 魏公村 国家图书馆 动物园 西直门2号线 积水潭 鼓楼大街 安定门 雍和宫 东直门 东四十条 朝阳门6号线 东大桥 呼家楼 金台路14号线东段 大望路 九龙山7号线 大郊亭 百子湾 化工 南楼梓庄 欢乐谷景区 双合 焦化厂
- 输入命令有误
-b 香山 -map 地铁线路信息.txt -o shortest.txt
错误命令！ 正确命令格式： 导入站点信息：java subway -map subway.txt 查询线路信息：java subway -a 1号线 -map subway.txt -o station.txt 查询站点间最短路程：java subway -b 站点1 站点2 -map subway.txt -o routine.txt
7、总结
Dijkstra还是不太熟悉，使用起来有些困难