北京地铁最短路径分析

地铁线路的信息保存在一份文本文档中，格式为：

地铁线路总数
线路名1 站名1 站名2 站名3 …
线路名2 站名1 站名2 站名3 …
线路名3 站名1 站名2 站名3 ……
地铁线路信息保存在train.txt中，格式如下：

项目需求
1：输入起点和终点要求能够输出最短路径站点总数以及详细的站点路线；
2：能够从文本中读取站点信息自动创建站点以及整理各个路线的站点

实现语言
Java

实现算法
DFS算法

相关类的功能描述
line:用于存储每条地铁线路的命名和存储线路中所有站点命名

public class line {
	private String name;//线路命名
	public ArrayList<String> linename=new ArrayList<String>();//线路中所有站点命名集合
}

station:用于存储站点的命名，所属的线路集合，临近的站点和与起点的距离

public class station {
	private String name;//站点的命名
	private ArrayList<String> linename=new ArrayList<String>();//站点所属线路集合
	public int cnt=-1;//距离起始点距离
	public station lastation;//临近的站点
}

核心代码
以下代码为简化代码，完整代码已上传至github

读取train.txt中的信息并存入station类和line类中

                        File file=new File(path);
			BufferedReader reader=new BufferedReader(new FileReader(file));
			String temp=null;
			while ((temp=reader.readLine())!=null) {
				String[] data=temp.split(" ");
				for(int i=1;i<data.length;i++) {
					boolean a=true;
					station statemp=new station();
					statemp.addLine(data[0]);
					statemp.setname(data[i]);
					for(station temp1:stationall) {
						if((temp1.getname()).equals(statemp.getname())) {
							temp1.addLine(data[0]);
							a=false;
						}
					}
					if(a==true)
						stationall.add(statemp);
				}
			}

			File file=new File(path);
			BufferedReader reader=new BufferedReader(new FileReader(file));
			String temp=null;
			int a=0;
			while ((temp=reader.readLine())!=null) {
				String[] data=temp.split(" ");
				line temp2=new line();
				temp2.setname(data[0]);
				for(int i=1;i<data.length;i++) {
					temp2.linename.add(data[i]);
				}
				lineall.add(temp2);
			}

执行BFS遍历，寻找出距离终点的最短路径
public static void findaround(station old,ArrayList<line> lineset,ArrayList<station> openlist,ArrayList<station> stationSet,int distance)//寻找与选定节点相邻的节点
public static boolean findend(ArrayList<station> openlist,station end)//判断终点是否进入了遍历节点openlist中

                while(!findend(openlist, end)) {
			ArrayList<station> openlist2=new ArrayList<>(); 
			for(station x2:openlist) {
				openlist2.add(x2);
			}
			for(station x1:openlist2) {
				findaround(x1, lineset, openlist, stationSet,distance);
			}
			distance++;
		}

根据最短路径和每个节点距离起始点的距离倒推回完整的路径
public static boolean isnear(station a,station b,ArrayList<line> lineset)//判断两个节点之间是否相邻

                station temp=new station();
		temp=end;
		while (distance>=0) {
			printlist.push(temp);
			temp=temp.lastation;
			distance--;
		}
		while (!(printlist.size()==1)) {
			System.out.print(printlist.pop().getname()+"-->");
		}
		System.out.print(printlist.pop().getname());

主函数如下

                public static void main(String[] args) {
		ArrayList<station> stationSet= new ArrayList<>(); 
		ArrayList<line> lineset=new ArrayList<>();
		ArrayList<station> openlist=new ArrayList<>();
		Stack<station> printlist=new Stack<>();
		String path="D:/train.txt";
		read(path,stationSet);
		readline(path, lineset);
		System.out.println("起点站");
		Scanner scan=new Scanner(System.in);
		String input=scan.next();
		System.out.println("终点站");
		String input2=scan.next();
		station start=new station();
		station end=new station();
		int distance=1;
		for(station temp:stationSet) {
			if(temp.getname().equals(input)) {
				start=temp;
				System.out.println("已找到起点站");
			}
		}
		for(station temp:stationSet) {
			if(temp.getname().equals(input2)) {
				end=temp;
				System.out.println("已找到终点站");
			}
		}
		openlist.add(start);
		start.cnt=0;
		findaround(start, lineset, openlist, stationSet,distance);
		while(!findend(openlist, end)) {
			ArrayList<station> openlist2=new ArrayList<>(); 
			for(station x2:openlist) {
				openlist2.add(x2);
			}
			for(station x1:openlist2) {
				findaround(x1, lineset, openlist, stationSet,distance);
			}
			distance++;
		}
		System.out.println("一共需要乘坐"+distance+"站");
		station temp=new station();
		temp=end;
		while (distance>=0) {
			printlist.push(temp);
			temp=temp.lastation;
			distance--;
		}
		while (!(printlist.size()==1)) {
			System.out.print(printlist.pop().getname()+"-->");
		}
		System.out.print(printlist.pop().getname());
	}

测试用例
1.起点站或者终点站不存在