java 实现地铁线路最短路径
提供一副地铁线路图，计算指定两站之间最短(最少经过站数)乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：
地铁线路总数
线路名1 站名1 站名2 站名3 ...
线路名2 站名1 站名2 站名3 ...
线路名3 站名1 站名2 站名3 ......
1.主要功能
两个功能：1.计算指定两站之间最短(最少经过站数)乘车路线；2.输出指定地铁线路的所有站点。
2.实现语言
`java`
3.最短路径实现算法
`Floyd` 算法(Floyd-Warshall algorithm)又称为弗洛伊德算法、插点法，
是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
4.相关类功能描述
类名称
功能
Station
站点
Line
地铁线路
Subway
读取文件、输出文件、计算最短路径
Main
主函数 识别命令参数运行程序
Stataion.java
private String stationName; //站点名称
private SetlineName; //所属地铁线
private SetlinkStations; //相连的地铁站
Line.java
private Liststations; //所经过站点
Main.java
//主函数
public static void main(String[] args) throws Exception {
//-map 地图读入
if(args[0].equals("-map")){
readfile(args[1]);
System.out.println("地图读取成功！");
}
// -a 地铁线站点输出
else if (args[0].equals("-a")){
readfile(args[3]);
Subway.check(args[1]);
//读取
Subway.outstation(args[1],args[5]);
System.out.println("车站信息输出成功！");
}
// -b 最短路径查询
else if(args[0].equals("-b")){
readfile(args[4]);
Subway.makeTb();
//读取输出文件，起点和终点
Subway.outroutine(args[6],args[1],args[2]);
System.out.println("路线信息输出成功！");
}
else{
System.out.println("请输入指定命令进行相应操作！");
}
}
Subway.java 会在核心代码部分详细说明
5.核心代码
1.读取文件
文件是每一行一条线路信息，所以用 readLine() 。
public static Set> readMetroline(String filename) throws Exception {
FileInputStream inputStream = new FileInputStream(filename);
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
Set>set=new HashSet>();
String str = null;
while ((str = bufferedReader.readLine()) != null) {
String[] lineInformations = str.split(" ");
Liststations=new ArrayList();
for (String s : lineInformations) {
stations.add(s);
}
set.add(stations);
}
inputStream.close();
bufferedReader.close();
return set;
}
2.查询某一条线路，在读取文件阶段就已经将信息都存储好了，直接查询就可以。
public static List check(String linename){
Line line=lines.get(linename);
Liststations=line.getStations();
Liststrings=new ArrayList();
for(Station station:stations){
strings.add(station.getStationName());
}
return strings;
}
计算最短路，使用弗洛伊德算法(核心部分)
public static void findFloydRoad(int[][] table) {
int size = len;
path = new int[size][size];
dist = new int[size][size];
//initialize dist and path
System.out.println(size);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
path[i][j] = -1;
dist[i][j] = table[i][j];
}
}
for (int k = 0; k < size; k++) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (dist[i][k] != INF &&
dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}
输出文件
public static void outstation(String linename,String fileName) throws Exception {
if(fileName.equals("")||fileName.equals(" ")){
System.out.println("输出文件名不能为空！");
}
else if(linename.equals("")||linename.equals(" ")){
System.out.println("查询线路名不能为空");
}
else {
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName)));
out.write(linename+"所经过的站点有");
out.newLine(); //换行
for (Station s : lines.get(linename).getStations()) {
out.write(s.getStationName());
out.newLine();
}
out.flush();
out.close();
}
}
public static void outroutine(String fileName,String a,String b) throws Exception {
if(fileName.equals("")||fileName.equals(" ")){
System.out.println("输出文件名不能为空！");
}
else {
int x =Station_num.get(a);
int y =Station_num.get(b);
findCheapestPath(x, y, table);
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName)));
out.write(" 从 " + subway_information.get(x).getStationName() + " 到 " + subway_information.get(y).getStationName() + " 一共历经" + dist[x][y] + "站" + " 的最佳路径是 ");
out.newLine(); //换行
for (int r : result) {
if (!subway_information.get(r).getStationName().equals(subway_information.get(x).getStationName())) {
out.write(" |");
out.newLine();
}
out.write(subway_information.get(r).getStationName());
out.newLine();
}
out.flush();
out.close();
}
}
6.测试用例
1.通过 -map 参数获得地铁的
2.查找五号线站点 -a 5号线 -map C://subway.txt -o -line.txt
3.查找最短路径 -b 出发站点 目的站点 -map C://subway.txt -o line.txt
7.总结
完成这一个小项目可以发现自己原本很多不足的地方，花费时间最多的是在文件的输入和输出上，经过这次的练习我对这方面有了更好的掌握。复习了计算最短路径一些算法，选择了使用弗洛伊德算法。在这个项目中也还要很多没有考虑到的，比如输出最短路线时没有考虑到换乘的说明。自己的代码能力还是不足，需要不断地练习。完整代码都放到 GitHub 上了，网址:https://github.com/wxzhyyy/Subway