个人项目--北京地铁线路规划(已完成）
一、任务：
实现一个帮助进行北京地铁出行路线规划的命令行程序。
二、设计信息
-
开发语言：JAVA
-
.算法：Dijkstra
- 功能设计框架
- 部分线路概览
三、需求分析及实现
-
需求1
-
在程序启动时，自动获取到地图信息
需要实现一个支持自动加载subway.txt 文件的程序
-
需求2
-
查询指定地铁线经过的站点
在应用程序上，需要支持一个新的命令行参数 -a ，指定用户希望查询的地铁线路。
在给定地铁线路时，程序需要从线路的起始站点开始，依次输出该地铁线经过的所有站点，直到终点站。输出的文件使用
-o参数来指定。一个调用应用程序的示例如下：
-
java subway -a 1号线 -map subway.txt -o station.txt
下为实际输出的station.txt 文件的内容
-
1 1号线 2 苹果园 3 古城 4 八角游乐园 5 八宝山 6 玉泉路 7 五棵松 8 ........
-
需求3
-
计算从出发到目的站点之间的最短路线并输出经过的站点的个数和路径
如果用户希望坐地铁，他希望能通过最少的站数从出发点到达目的地，这样就可以在命令行中以 -b 参数加两个地铁站点名称分别作为出发与目的，命令让程序将结果写入 routine.txt 中。程序将计算从出发到目的站点之间的最短(经过的站点数最少)路线，并输出经过的站点的个数和路径(包括出发与目的站点)。如果需要换乘，会在换乘站的下一行输出换乘的线路。输出的文件使用-o参数来指定。
一个调用应用程序的示例如下：
java subway -b 玉泉路 白石桥南 -map subway.txt -o routine.txt
运行结果输出如下:
1 地铁：1号线
2 五棵松
3 万寿路
4 公主坟
5 军事博物馆
6 地铁：9号线
7 白堆子
8 白石桥南
四、逻辑实现
-
数据预处理
- 数据在txt文件中的记录以如下格式呈现：
13：14号线东段：北京南站，永定门外，景泰，蒲黄榆，方庄，十里河，北工大西门，平乐园，九龙山，大望路，金台路，朝阳公园，枣营，东风北桥，将台，望京南，阜通，望京，东湖渠，来广营，善各庄
14：15号线：清华东路西口，六道口，北沙滩，奥林匹克公园，安立路，大屯路东，关庄，望京西，望京，望京东，崔各庄，马泉营，孙河，国展，花梨坎，后沙峪，南法信，石门，顺义，俸伯
15：16号线：北安河，温阳路，稻香湖路，屯佃，永丰，永丰南，西北旺，马连洼，农大南路，西苑
16：八通线：四惠，四惠东，高碑店，传媒大学，双桥，管庄八里桥，通州北苑，果园，九棵树，梨园，临河里，北桥
17：昌平线：昌平西山口，十三陵景区，昌平，昌平东关，北邵洼，南邵，沙河高教区，沙河，巩华城，朱辛庄，生命科学园，西二旗
18：亦庄线：宋家庄，肖村，小红门，旧宫，亦庄桥，亦庄文化园，万源街，容京东街，荣昌东街，同济南路，经海路，次渠南，次渠，亦庄火车站
................
- 在读取了文件中的数据后，首先以 ”： “ 作为分隔，将每一行的数据分为三部分，第一部分为每条地铁的标号，第二部分为每条地铁的名称，第三部分为每条地铁的站点信息。
- 程序将识别所有的转乘站点，作为一个结点，这样可以避免在计算最短路径过程中，将所有站点的距离都计算一遍。并且，由于北京地铁的特殊性，有些地铁线路为环状线路，我们需要把成环的线路检测出来，并且以map的形式记录其编号和线路总长度在这里。
- 为了方便后续的路径计算，我们以距离为模拟将每个站点计算出其编号，公式为（地铁线路标号*1000 + 当条地铁线第几个站点 +1）。若该地铁为环状地铁线路，则将 其编号乘以（-1），以便在计算最短路径时候可以知道这是一条环线，并采用不同的最短计算方式。
- 数据加载预处理的方法函数如下：
public void loadLineFile()
// 加载地铁线路数据
public void loadLineFile(String strSubwayFileName) {
File fSubway = new File(strSubwayFileName);
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(fSubway));
String tempString = null;
while ((tempString = reader.readLine()) != null) {
if (tempString.startsWith("\uFEFF")) {
tempString = tempString.substring(1, tempString.length());
}
listSubwayInfo.addElement(tempString);
}
System.out.println("成功加载地铁线路文件！\n");
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
parseSubwayStationsData();
}
void parseSubwayStationsData()
void parseSubwayLineData()
// 地铁数据处理
void parseSubwayStationsData() {
for (String strSubwayLine: listSubwayInfo) {
parseSubwayLineData(strSubwayLine);
}
}
void parseSubwayLineData(String strSubwayLine) {
String[] arrLineAndStations = strSubwayLine.split("："); // 划分地铁线路和该线路所有站点
if (arrLineAndStations.length != 3) {
System.out.println("地铁数据错误" + strSubwayLine);
return;
}
int nLine = getLineNumber(arrLineAndStations[0]);
stationInfo.put(nLine,arrLineAndStations[1]);
if (nLine == -1) {
System.out.println("地铁线路号数据错误" + strSubwayLine);
}
String[] arrStrStationNames = arrLineAndStations[2].split("，");
System.out.println(arrStrStationNames[0]+" "+arrStrStationNames[arrStrStationNames.length-1]);;
if(arrStrStationNames[0].equals(arrStrStationNames[arrStrStationNames.length-1]))
{
for (int i=0; i < arrStrStationNames.length-1; i++) {
String strStationName = arrStrStationNames[i];
int nStationId = -(nLine*1000 + i+1);
circleInfo.put(nLine,arrStrStationNames.length-1 );
Station station = new Station();
station.stationName = strStationName;
station.setStationId.add(nStationId);
mapStationIdtoStation.put(nStationId, station);
if (!mapNametoStation.containsKey(strStationName)) {
mapNametoStation.put(strStationName, station);
} else {
// 如果站点名字存在，证明是中转站
Station stationExistedTransferStation = mapNametoStation.get(strStationName);
stationExistedTransferStation.setStationId.add(nStationId);
mapTransferStationNametoDistance.put(stationExistedTransferStation.stationName, nMaxDistance);
}
}
}
for (int i=0; i < arrStrStationNames.length; i++) {
String strStationName = arrStrStationNames[i];
int nStationId = nLine*1000 + i+1;
Station station = new Station();
station.stationName = strStationName;
station.setStationId.add(nStationId);
mapStationIdtoStation.put(nStationId, station);
if (!mapNametoStation.containsKey(strStationName)) {
mapNametoStation.put(strStationName, station);
} else {
// 如果站点名字存在，证明是中转站
Station stationExistedTransferStation = mapNametoStation.get(strStationName);
stationExistedTransferStation.setStationId.add(nStationId);
mapTransferStationNametoDistance.put(stationExistedTransferStation.stationName, nMaxDistance);
}
}
}
迪杰斯特拉算法求最短路径
-
操作步骤
-
初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
-
从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
-
更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
-
重复步骤(2)和(3)，直到遍历完所有顶点。
- 由于北京地铁的一些地铁线路为环形线，并且在先前做数据预处理的时候，已经将环形的编号编为负值，所以当我们在计算站点时，若遇到两个负值的站点，且距离的绝对值小于1000，则说明其在同一条环线上，两站点的距离应取为 min( abs(站点1_id – 站点2_id), 地铁线路长度-abs(站点1_id – 站点2_id))。
- 同时，在计算最短路径的同时，要保存每个结点最后被更新前的上一个结点，这样可以方便我们后续输出其完整路径。
以下为迪杰斯特拉算法计算最短路径的方法函数：
Path Dijkstra()
// 最优路径规划
Path Dijkstra(String strStartStationName, String strEndStationName) {
// todo: 进行一些合法性检查
Station stationStart = mapNametoStation.get(strStartStationName);
Station stationEnd = mapNametoStation.get(strEndStationName);
if(stationStart==null || stationEnd==null)
{
System.out.println("起始站或终点输入不正确，请检查输入数据！");
return null;
}
mapTransferStationNametoDistance.put(strEndStationName, nMaxDistance);
mapTransferStationNametoDistance.put(strStartStationName, nMaxDistance);
Path pathStart = new Path();
pathStart.nFDistance = 0;
pathStart.stationLastStationInPath = stationStart;
Path Dijkstra = new Path();
Dijkstra.nFDistance = nMaxDistance;
Stack<Path> stackAllPaths = new Stack<>();
stackAllPaths.push(pathStart);
Set<String> TStationNameSet = new TreeSet<>();
for(String strname: mapTransferStationNametoDistance.keySet()) {
TStationNameSet.add(strname);
}
for(String strname: mapTransferStationNametoDistance.keySet()) {
finalMap.put(strname,"null");
}
while (!stackAllPaths.empty()) {
Path pathCurrent = stackAllPaths.pop();
if (pathCurrent.nFDistance > Dijkstra.nFDistance) {
continue;
}
int nBDistance = getStationsDistance(pathCurrent.stationLastStationInPath, stationEnd);
if (nBDistance == 0) { // 到达终止节点
if (pathCurrent.nFDistance < Dijkstra.nFDistance) {
Dijkstra = pathCurrent;
}
continue;
}
int minDistance = 1000000;
String nextStation = null;
TStationNameSet.remove(pathCurrent.stationLastStationInPath.stationName);
for (String strTStationName: mapTransferStationNametoDistance.keySet()) {
Station stationTransfer = mapNametoStation.get(strTStationName);
int nDistanceDelta = getStationsDistance(pathCurrent.stationLastStationInPath, stationTransfer);
int nTStationDistance = pathCurrent.nFDistance + nDistanceDelta;
if (nTStationDistance >= mapTransferStationNametoDistance.get(strTStationName)) {
continue;
}
finalMap.put(strTStationName,pathCurrent.stationLastStationInPath.stationName);
mapTransferStationNametoDistance.put(strTStationName, nTStationDistance);
}
for(String strTStationName: mapTransferStationNametoDistance.keySet()) {
int Distance = mapTransferStationNametoDistance.get(strTStationName);
if(Distance<minDistance&& TStationNameSet.contains(strTStationName)) {
minDistance = Distance;
nextStation = strTStationName;
}
}
Station stationTransfer = mapNametoStation.get(nextStation);
Path pathNew = new Path();
pathNew.nFDistance = minDistance;
pathNew.stationLastStationInPath = stationTransfer;
stackAllPaths.push(pathNew);
}
System.out.println(finalMap);
return Dijkstra;
}
打印路径 &打印指定地铁线路
- 在计算最短路径的时候，已经保存了每个站点最后被更新时的上一个结点，这个时候，只要我们循环从最后一个结点往回找，就可以得到最终”倒序“的路径了，这里有一个小技巧，为了避免再写一个linkedhashmap 的倒序，这里我们可以直接在输入起点和终点的时候，程序将起点和终点交换，这样就可以得到（倒序（倒序）=正序）的效果了。
- 同时在打印两个中间转站点之间的站点时，当两个站点的id差值为正的时候，就将step设置为正1，每次加1，并通过得到的编号输出站点名；同样，当两个站点的id 差值为负的时候，就将step设置为-1即可,最后，通过计算出的地铁线路编号和地铁名称的map，输出地铁名称以及地铁线路的信息,最后将其输入到txt文件中去。
stationsInLine()
Vector<String> stationsInLine(Station stationStart, Station stationEnd) {
Vector<String> listStations = new Vector<String>();
int nLineNumber = getLineNumber(stationStart, stationEnd);
int nStartId = 0;
int nEndId = 0;
for (int nId: stationStart.setStationId) {
if (Math.abs(nId-(nLineNumber*1000))<1000) {
nStartId = nId;
}
}
for (int nId: stationEnd.setStationId) {
if (Math.abs(nId-(nLineNumber*1000))<1000) {
nEndId = nId;
}
}
if (nStartId == nEndId) {
return listStations;
}
int nStep = 1;
if (nEndId < nStartId) {
nStep = -1;
}
int nIndexId = nStartId + nStep;
while (nIndexId != nEndId) {
String strSName = mapStationIdtoStation.get(nIndexId).stationName;
listStations.addElement(strSName);
nIndexId += nStep;
}
String strName = mapStationIdtoStation.get(nEndId).stationName;
listStations.addElement(strName);
return listStations;
}
void printPath()
void printPath(String start,String end, String strOutFileName) {
String strFormatedPath = formatPath(start,end);
toFile(strFormatedPath, strOutFileName);
}
formatPath()
String formatPath(String start,String end) {
StringBuffer strRst = new StringBuffer();
int nCurrentLine = -1;
System.out.print(finalMap);
while(end != finalMap.get(end)) {
Station stationStart = mapNametoStation.get(end);
Station stationEnd = mapNametoStation.get(finalMap.get(end));
end = finalMap.get(end);
int nLineNum = Math.abs(getLineNumber(stationStart, stationEnd));
if (nLineNum != nCurrentLine) {
nCurrentLine = nLineNum;
strRst.append(String.format("地铁：%s\r\n", stationInfo.get(nLineNum)));
}
for (String strStationName: stationsInLine(stationStart, stationEnd)) {
strRst.append(String.format("%s\r\n", strStationName));
}
}
return strRst.toString();
}
void toFile()
void toFile(String strContent, String strOutFile) {
try {
File file = new File(strOutFile);
if (!file.exists()) {
file.createNewFile();
}
FileWriter fileWriter = new FileWriter(file.getName(), false);
fileWriter.write(strContent.toString());
fileWriter.close();
} catch (IOException e) {
e.printStackTrace();
}
};
printLineInfo()
void printLineInfo(String LineName, String strOutFile) {
StringBuffer strRst = new StringBuffer();
// strRst.append(String.format("%s\r\n", stationInfo.get(nLineNum)));
strRst.append(String.format("%s\r\n", LineName));
if(NtostationInfo.get(LineName)==null)
{
System.out.println("不存在该条地铁线路，请检查输入！");
return;
}
int nLineNum = NtostationInfo.get(LineName);
for (int i = 1; i < 90; i++) {
int nStationId = nLineNum * 1000 + i;
if (mapStationIdtoStation.containsKey(nStationId)) {
strRst.append(mapStationIdtoStation.get(nStationId).stationName + "\r\n");
} else {
break;
}
}
toFile(strRst.toString(), strOutFile);
}
五、测试
- -map 后没有参数信息
java subway -b 玉泉路 白石桥南 -map
- 2.缺少输出文件信息
java subway -b 玉泉路 白石桥南 -map subway.txt -o
- 3.缺少起点或终点信息
java subway -b 玉泉路 -map subway.txt -o routine
- 4.查询的地铁线路不存在
java subway -a 昌平 -map subway.txt -o station.txt
- 5.查询的地铁起点或终点站不存在
java subway -b 万安 知春 -map subway.txt -o routine.txt
- 6.查询指定地铁线路并输出到station.txt
java subway -a 昌平线 -map subway.txt -o station.txt
输出的station.txt文件内容：
1 地铁：昌平线
2 昌平西山口
3 十三陵景区
4 昌平
5 昌平东关
6 北邵洼
7 南邵
8 沙河高教区
9 沙河
10 巩华城
11 朱辛庄
12 生命科学园
13 西二旗
- 7.查询的起点终点在同一条地铁线上
java subway -b 六道口 望京东 -map subway.txt -o routine.txt
输出的station.txt文件内容：
地铁：15号线
北沙滩
奥林匹克公园
安立路
大屯路东
关庄
望京西
望京
望京东
- 8.查询的起点终点不在同一条地铁线上
java subway -b 古城 菜市口 -map subway.txt -o routine.txt
输出的station.txt文件内容：
地铁：1号线
八角游乐园
八宝山
玉泉路
五棵松
万寿路
公主坟
军事博物馆
地铁：9号线
北京西站
地铁：7号线
湾子
达官营
广安门内
菜市口
9.查询的起点终点不在同一条地铁线上，且起点或终点在一条环形线路上
java subway -b 万安 知春里 -map subway.txt -o routine.txt
输出的station.txt文件内容：
地铁：西郊线
茶棚
颐和园西门
巴沟
地铁：10号线
苏州街
海淀黄庄
知春里
六、项目完成时间统计
| Personal Software Process Stages | Time | Real time | |
|---|---|---|---|
|
计划与需求分析 |
1 day | 1h | |
|
开发 |
10 days | 15h | |
|
代码规范 |
1 day | 1h | |
|
设计文档 |
1 day | 1h | |
|
测试 |
1 day |
2h |
|
|
报告 |
1 day | 7h | |
|
总结并提出改进计划 |
1 day | 1h | |
| 合计 | 16 days | 28h | |
七.总结
这是我第一用java编写数据结构的算法，也是我第一次用数据结构做一个有实际意义的小项目。在本次北京地铁路径的规划中，只将换乘站和起点终点作为需要计算的结点，从而免去了计算所有站点所带来的时间负杂度，并且直接使用编号的办法进行距离的计算，我觉得是本次项目的亮点。但是，在设计过程中，也遇到了不少麻烦，比如说用编号表示距离的方法，会带来一个问题，由于北京地铁的一些线路是环形的，而我们给的subway.txt 文件中，是顺序存储每个线路站点的，这样就会导致近在眼前的站点，从编号上来计算距离却远在天边，但是后来通过检测环状线路，并用取编号差和线路长度减编号差的小值作为两站点之间的线路就很好的解决了这个问题。总之，通过本次项目实验，让我体会到了作为一个程序员，理论和实践相结合的重要性，同时要学会细心观察，强化程序的健壮性和实用性。
github代码地址：https://github.com/syxaa/syx_subway
版权声明：本文为jamessyx原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。