#### 项目介绍
##### 主要功能
提供一副地铁线路图，计算指定两站之间最短（最少经过站数）乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：
地铁线路总数线路名1 站名1 站名2 站名3 ...线路名2 站名1 站名2 站名3 ...线路名3 站名1 站名2 站名3 ......
Java
首先将地铁线路信息载入处理，当要寻找两个站点最短路径时，先查找存储最短路径的文件中是否存在该两站点的最短路径记录，如没有再找到连通两站点的所有的线路路径（线路不得重复，线路数亦不可大于地铁线路总数），再根据所提供的线路路径去寻找两条线路间的换乘站点，比较所经站点的数量，选择站点数最少的路径；如存在站点数相同，则选择经过线路最少的路径；如所经线路相同，则都输出。
BeanStation 站点的相关信息
BeanLine 线路的相关信息
BeanPath 路径的相关信息
LineManager 关于BeanLine的一些函数
StationManager 关于BeanStation的一些函数
MyUtil 调用LineManager和StationManager
Stater 主类（读写文件和运行程序）
（1） BeanStation
private int id; //站点id
private String StationName; //站点名
private boolean isTransferStation; //是否是换乘站点
private List<BeanLine> onLine = new ArrayList<>(); //所在线路
(2) BeanLine
private int id; //线路id
private String LineName; //线路名
private boolean isLoop; //是否是回环线路
private List<BeanStation> stationList = new ArrayList<>(); //所经站点
private Set<BeanLine> connectedLine = new HashSet<>(); //相连线路
private int[][] Graph; //线路内站到站的最短距离
(3) BeanPath
private String beginStation; //起始站
private String endStation; //终点站
private List<BeanStation> aStations = new ArrayList<>(); //所经站点
private int sumSations;
private List<BeanLine> aList = new ArrayList<>(); //所经线路
(4) 根据路线和起始站、终点站确定所经站点
public BeanPath thronghStations(BeanPath path,Map<String, BeanStation> nameToStation,Map<Integer, BeanLine> idToLine){
if(path.getBeginStation().equals(path.getEndStation())) {
path.getaStations().add(nameToStation.get(path.getEndStation()));
path.setSumSations(0);
return path;
}
else if (path.getaList().size()==1) {
int l=distanceBetwwenTwoStations(path.getaList().get(0), nameToStation.get(path.getBeginStation()), nameToStation.get(path.getEndStation()));
path.getaStations().add(nameToStation.get(path.getEndStation()));
path.getaStations().add(nameToStation.get(path.getBeginStation()));
path.setSumSations(l);
return path;
}
else {
BeanStation nowStation= nameToStation.get(path.getBeginStation());
List<BeanLine> list = path.getaList().subList(0, path.getaList().size()-1);
for(BeanStation station: path.getaList().get(path.getaList().size()-1).getStationList()) {
if(!station.getStationName().equals(path.getBeginStation())&&station.isTransferStation()) {
if(station.getOnLine().contains(list.get(list.size()-1))) {
BeanPath newPath = new BeanPath(station.getStationName(), path.getEndStation());
newPath.setaList(list);
BeanPath newPath2 = thronghStations(newPath, nameToStation, idToLine);
int l=distanceBetwwenTwoStations(path.getaList().get(path.getaList().size()-1), nameToStation.get(path.getBeginStation()), station);
if(path.getaStations().isEmpty()) {
path.setaStations(newPath2.getaStations());
path.getaStations().add(nowStation);
path.setSumSations(newPath2.getSumSations()+l);
}else if(l+newPath2.getSumSations()<path.getSumSations()) {
path.setaStations(newPath2.getaStations());
path.getaStations().add(nowStation);
path.setSumSations(newPath2.getSumSations()+l);
}
}
}
}
return path;
}
}
(5) 查找如何从一条线路到另一条线路
public List<List<BeanLine>> LineToLine(BeanLine start, BeanLine end, int n){
List<List<BeanLine>> array = new ArrayList<>();
if(n==0) return array;
if(start.getId()==end.getId()) {
List<BeanLine> aLines = new ArrayList<>();
aLines.add(start);
array.add(aLines);
return array;
}
for(BeanLine line: start.getConnectedLine()) {
if(line!=start) {
List<List<BeanLine>> l2l = LineToLine(line, end,n-1);
if(l2l.isEmpty()) continue;
for(List<BeanLine> aLines: l2l) {
if(aLines.contains(start)) l2l.remove(aLines);
else{
aLines.add(start);
if(!array.contains(aLines)) array.add(aLines);
}
}
}
}
return array;
}
(6) 根据线路信息创建图（BeanLine,Floyd)
public void createGraph(){
int length = stationList.size();
Graph = new int[length][length];
for(int i=0;i<length;i++){ //初始化图
for(int j=0;j<=i;j++){
Graph[i][j]=Graph[j][i]=i-j;
}
}
if(isLoop==true){ //当线路为环路时要修改站与站的距离
Graph[0][length-1]=Graph[length-1][0]=1;
for(int i=0;i<length;i++){
for(int k=0;k<length;k++){
for(int j=0;j<length;j++){
if(i!=j&&i!=k&&j!=k){
if(Graph[i][j]>Graph[i][k]+Graph[j][k])
Graph[i][j]=Graph[j][i]=Graph[i][k]+Graph[j][k];
}
}
}
}
}
}
（7）Starter
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import control.LineManager;
import model.BeanLine;
import model.BeanPath;
import model.BeanStation;
import util.MyUtil;
public class Starter {
List<BeanStation> stations = new ArrayList<>(); //存放所有站
List<BeanStation> transferStations = new ArrayList<>(); //存放换乘站点
List<BeanLine> lines = new ArrayList<>(); //存放所有线路
Map<String, BeanStation> nameToStationMap = new HashMap<>(); //由站名映射站
Map<Integer, BeanLine> idToLineMap = new HashMap<>(); //由线路id映射线路
Map<String, BeanLine> nameToLineMap = new HashMap<>(); //由线路名映射线路
//载入地铁线路信息
public void loadInformation() {
String pathName = "地铁线路信息.txt";
try {
BufferedReader br=new BufferedReader(new InputStreamReader(new FileInputStream(pathName),"UTF-8"));
String string;
while((string=br.readLine())!=null) {
String[] a = string.split(" ");
int lineId = lines.size();
String lineName = a[0];
BeanLine line = new BeanLine(lineId, lineName);
idToLineMap.put(lineId, line);
nameToLineMap.put(lineName, line);
for(int i=1;i<a.length;i++) {
if(nameToStationMap.containsKey(a[i])) { //查看站点是否曾出现过
BeanStation s = nameToStationMap.get(a[i]);
if(!s.isTransferStation()) s.setTransferStation(true); //如果不是换乘站点就设置成换乘站点
if(!transferStations.contains(s)) transferStations.add(s);
s.getOnLine().add(line);
line.getStationList().add(s);
}
else {
int stationId=stations.size();
BeanStation station = new BeanStation(stationId, a[i]);
nameToStationMap.put(a[i], station);
stations.add(station);
line.getStationList().add(station);
station.getOnLine().add(line);
}
}
if(a[1].equals(a[a.length-1])) line.setLoop(true);
line.createGraph();
lines.add(line);
}
br.close();
} catch (Exception e) {
e.printStackTrace();
}
}
//查询已确定的最短路线中是否已存在需求路线
public boolean shortestPath(String startStation, String endStation) {
String pathName = "已确定的最短路径.txt";
try {
BufferedReader br=new BufferedReader(new InputStreamReader(new FileInputStream(pathName),"UTF-8"));
String string;
while((string=br.readLine())!=null) {
String[] a = string.split(" ");
if(a[0].equals(startStation)&&a[1].equals(endStation)) {
System.out.println(string);
return true;
}
}
br.close();
} catch (Exception e) {
e.printStackTrace();
}
return false;
}
//显示路径并写入文件
public void writeFile(BeanPath path) {
try {
File file = new File("已确定的最短路径.txt");
if (!file.exists())
file.createNewFile();
BufferedWriter out = new BufferedWriter(new FileWriter(file,true));
System.out.println(path.toString());
out.write(path.toString()+"\r\n");
out.flush(); // 把缓存区内容压入文件
out.close();
}
catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
Starter starter = new Starter();
starter.loadInformation();
for(BeanStation s: starter.transferStations) {
for(BeanLine l: s.getOnLine()) {
MyUtil.lineManager.addConnectedLines(s.getOnLine(), l);
}
}
Scanner input = new Scanner(System.in);
System.out.print("请输入起始站：");
String begin = input.nextLine().trim();
System.out.print("请输入终点站：");
String end = input.nextLine().trim();
if(!(starter.nameToStationMap.containsKey(begin)&&starter.nameToStationMap.containsKey(end))) {
System.out.println("站名不存在");
System.exit(0);
}
if(!starter.shortestPath(begin, end)) {
BeanStation s1=starter.nameToStationMap.get(begin);
BeanStation s2=starter.nameToStationMap.get(end);
List<List<BeanLine>> allLines = new ArrayList<>();
for(BeanLine l1: s1.getOnLine()) {
for(BeanLine l2: s2.getOnLine()) {
allLines.addAll(MyUtil.lineManager.LineToLine(l1, l2,23));
}
}
List<BeanPath> allPaths = new ArrayList<>();
for(List<BeanLine> line: allLines) {
BeanPath path = new BeanPath(begin, end);
path.setaList(line);
path = MyUtil.stationManager.thronghStations(path, starter.nameToStationMap, starter.idToLineMap);
allPaths.add(path);
}
Comparator<BeanPath> com = new MyComparator();
Collections.sort(allPaths, com);
if(allPaths.isEmpty()) {
System.out.println("无可选路线");
}else {
starter.writeFile(allPaths.get(0));
for(int i=1;i<allPaths.size();i++) {
if(allPaths.get(i).getSumSations()==allPaths.get(0).getSumSations()&&allPaths.get(i).getaList().size()==allPaths.get(0).getaList().size()) {
starter.writeFile(allPaths.get(i));
}
}
}
}
}
}
//自定义函数，按所经站点从少到多排序，如相同，则按所经线路从少到多排序
class MyComparator implements Comparator<BeanPath> {
public int compare(BeanPath p1,BeanPath p2) {
if(p1.getSumSations()!=p2.getSumSations()) return p2.getSumSations()-p1.getSumSations();
else {
return p2.getaList().size()-p1.getaList().size();
}
}
}
(1)
(2)
(3)
(4)
这次作业让我对java有了更深的了解，明白了一些类在调用时需要注意的地方，并通过网上学习知道了如何去避免或是解决问题
在编程实践中总能找到本以为自己会却做不到的地方
代码依旧存在一些问题未解决，且有机会的话我会把ui补上
github地址：https://github.com/onshero/SubwayShortestPath
原文：https://www.cnblogs.com/onshero/p/13931040.html