所有代码已上传至本人的github账号：点击此处查看完整代码
本篇文章包含了“地铁最短线路”的代码、对代码结构的解析，以及代码的测试样例。
一、主要功能
程序功能大体分为三部分：
- 读取地铁线路信息并显示
- 读取用户输入的站点名称
- 计算站点间最短路径并显示
二、实现语言
本程序使用java语言实现
三、实现算法
在建立地铁线路图时，我使用了“无权”路径来描述，即地铁个各站点之间的距离都为“1”。所以我使用了BFS来求解最短路径。(若考虑站点间距离，则图的边有权值，也可使用Dijkstra算法来解决问题)
四、类功能划分
- Start类
是整个程序的入口类，在main方法中，创建了一个AllMethod实例
public class Start {
public static void main(String[] args) {
AllMethod method=new AllMethod();
}
}
- Station类
用于存储站点的各种信息。包括站点名称，站点所在各个线路名称，该站点的各个相邻站点信息，站点的前驱节点及站点到起始站的距离。 ( 已省略eclipse自动生成的get()set()函数 )
public class Station {
private String stationName=null;
private List<String> stationLine=new ArrayList<String>();//站点所在线路
private List<Station> stationLink=new ArrayList<Station>();//相邻站点
public Station pre=null;//前驱节点
public int dist;
public void addStationLine(String line) {
stationLine.add(line);
}
public void addStationLink(Station station) {
stationLink.add(station);
}
}
- Line类
用于存储线路的各种信息。包括线路名称，及线路所包含的各个站点名称。 ( 已省略eclipse自动生成的get()set()函数 )
public class Line {
private String lineName=null;
private List<String> stations=new ArrayList<String>();
public void addStation(String stationName) {
stations.add(stationName);
}
}
- AllMethod类
包含了实现程序主要功能的大部分方法 ( 详细方法代码将在第五部分 核心代码中 )
public class AllMethod {
final int MaxNum=1000;
final int MaxValue=100000;
public List<Station> stations=new ArrayList<Station>();
public List<Line> lines=new ArrayList<Line>();
public List<Station> shortestPath=new ArrayList<Station>();
public File file=null;
public Station startStation=new Station();
public Station endStation=new Station();
public AllMethod() {
readFile();//读取文件
dataInit();//数据初始化
printLines();//输出所有地铁线路
inputStation();//输入起始站及终点站
buildPath(endStation);//计算最短路线
printShortestLine();//输出最短路径
}
}
五、核心代码
- 读取文件
public void readFile() {
file=new File("station.txt");
}
- 数据初始化。将文件中的内容提取出来，保存进
Station类及Line类的实例中
public void dataInit() {
try {
InputStreamReader read=new InputStreamReader(new FileInputStream(file),"UTF-8");
BufferedReader reader=new BufferedReader(read);
String stationName=null;
while((stationName=reader.readLine())!=null) {//一行为一条线路
int j;
Station lastStation=null;
String line_station[]=stationName.split(" ");
Line line=new Line();
line.setLineName(line_station[0]);//线路名字为第一个读入的字符串
for(int i=1;i<line_station.length;i++) {//从第二个读入的字符串之后，都是站点名
line.addStation(line_station[i]);//将站点加入线路
for(j=0;j<stations.size();j++) {
if(stations.get(j).getStationName().equals(line_station[i])) {//判断车站是否已存在
stations.get(j).addStationLine(line.getLineName());
if(i!=1) {
stations.get(j).addStationLink(lastStation);
lastStation.addStationLink(stations.get(j));
}
lastStation=stations.get(j);
break;
}
}
if(j==stations.size()) {//车站不存在
Station station=new Station();
station.addStationLine(line_station[0]);
station.setStationName(line_station[i]);
station.dist=MaxValue;//?
if(i!=1) {
station.addStationLink(lastStation);
lastStation.addStationLink(station);
}
stations.add(station);
lastStation=station;
}
}
lines.add(line);
}
}catch(UnsupportedEncodingException e1) {
e1.printStackTrace();
}catch(FileNotFoundException e2) {
e2.printStackTrace();
}catch(IOException e3) {
e3.printStackTrace();
}
}
- 输出所有地铁线路
public void printLines() {
for(int i=0;i<lines.size();i++) {
Line line=lines.get(i);
System.out.print(line.getLineName());
for(int j=0;j<line.getStations().size();j++) {
System.out.print("\t"+line.getStations().get(j));
}
System.out.println();
}
}
- 输入起始站及终点站。起始站输入完毕后，马上用BFS方法计算所有站点到起始站的最短路线
public void inputStation() {
Scanner input=new Scanner(System.in);
int index;
String start=null;
String end=null;
System.out.println("\n站点间最短路径查询\n");
do {
System.out.print("请输入起始站：");
start=input.nextLine().replace(" ", "");
//startStation.setStationName(input.nextLine().replace(" ", ""));
} while (!((index=isExist(start))<MaxNum));
startStation=stations.get(index);
bfsShortestPath(startStation);
do {
System.out.print("请输入终点站：");
end=input.nextLine().replace(" ", "");
//endStation.setStationName(input.nextLine().replace(" ", ""));
} while (!((index=isExist(end))<MaxNum));
endStation=stations.get(index);
}
public void bfsShortestPath(Station station) {
Queue<Station> queStation=new LinkedList<>();
station.dist=0;
queStation.offer(station);
while(!queStation.isEmpty()) {
Station s=queStation.poll();
for(int i=0;i<s.getStationLink().size();i++) {
if(s.getStationLink().get(i).getDist()==MaxValue) {
s.getStationLink().get(i).setDist(s.dist+1);
queStation.offer(s.getStationLink().get(i));
s.getStationLink().get(i).setPre(s);
}
}
}
}
- 计算最短路线
public void buildPath(Station theEnd) {
if(theEnd.getPre()!=null) {
buildPath(theEnd.getPre());
}
shortestPath.add(theEnd);
}
- 输出最短路径
public void printShortestLine() {
String changeLine=getSameLine(shortestPath.get(0), shortestPath.get(1));
System.out.println("\n"+changeLine+":");
for(int i=0;i<shortestPath.size();i++) {
if(i>=2) {
Station station1,station2;
station1=shortestPath.get(i);
station2=shortestPath.get(i-1);
if(!getSameLine(station1, station2).equals(changeLine)) {
changeLine=getSameLine(shortestPath.get(i), shortestPath.get(i-1));
System.out.println("\n换乘 "+changeLine+":");
System.out.print(shortestPath.get(i).getStationName());
continue;
}
}
if(i!=0) {
System.out.print(" --> ");
}
System.out.print(shortestPath.get(i).getStationName());
}
}
六、测试用例**输入前显示的所有站点及线路名称**
1.输入错误
2.不用换乘
3.需要换乘
七、总结
使用BFS求解最短路径仅能求出其中一条，可以用Dijkstra算法进行改进