项目介绍
完整代码地址https://github.com/XintongDou/SubwayShortestRoute
1.主要功能
提供一副地铁线路图，计算指定两站之间最短（最少经过站数）乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：
地铁线路总数
线路名1 站名1 站名2 站名3 ...
线路名2 站名1 站名2 站名3 ...
线路名3 站名1 站名2 站名3 ......
2. 实现语言
java
3. 实现算法
广度优先搜索（BFS）
4. 类职责划分
BeanStation类
存储地铁站信息
public class BeanStation {
private String stationName;// 站名
private List
private List
}
BeanRoute类
存储路径中的结点信息
public class BeanRoute {
private BeanStation startStation; // 起始站
private BeanStation endStation; // 终点站
private BeanStation lastStation; // 到达该站的最短路径中的上一站
private int distance; // 距离
private String line; // 到达该站在几号线上
private int linechange; // 上一站到这一站是否换乘，换乘则为1，不换乘则为0
}
DataProcessing类
用于数据读入和处理
变量声明
// 储存线路集合，其中的每个元素都是一条线路
public static LinkedHashSet<List
方法声明
//处理数据，处理站点信息
public DataProcessing() throws IOException {}
Subway类
用于计算最短路径
变量声明
private static List
private static HashMap<BeanStation, BeanRoute> routeMap = new HashMap<>(); // 路径集
方法声明
private static BeanStation getnextStation() {} // 选择下一个需要BFS的站点
private static List
public static BeanRoute BFS(BeanStation startStation, BeanStation endStation) {} // BFS计算最短路径
public static List
SubwayShortestRoute类
main函数所在的类，负责读入用户的输入和输出最短路径信息。
5. 核心代码
public DataProcessing() throws IOException {
String pathname = "data.txt";// 地铁线路信息的地址
File filename = new File(pathname); // 将给定路径名字符串转换成抽象路径名来创建一个新的File实例
// 读取文件：FileInputStream以字节形式读入文件
// InputStreamReader将读入的字节转化为字符
// BufferedReader从字符输入流中读取文本并缓冲字符，以便有效地读取字符，数组和行
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(filename), "UTF-8"));
int linenum = Integer.parseInt(br.readLine());// 读取一共有多少条线路，将读入的字符串转换为int类型
for (int i = 0; i < linenum; i++) {// 循环读入线路信息
String content = br.readLine();
List<BeanStation> line = new ArrayList<BeanStation>();
// 按“ ”空格分割读入的内容，分割出线路名和之后的一串站名
String[] word = content.split(" ");
String linename = word[0];
int length = word.length;
for (int j = 1; j < length; j++) {// 循环添加站点
BeanStation newStation = new BeanStation();
int changeable = 0;
// 遍历已输入的线路信息，判断该站是否为换乘站
for (List<BeanStation> l : lineSet) {
int size = l.size();
for (int k = 0; k < size; k++) {// 遍历线路中的站点
// 判断站名是否相同
if (l.get(k).getStationName().equals(word[j])) {
// 站名重复，将线路名添加到该站点的所在站点（List<String> line）中
l.get(k).addLine(linename);
newStation = l.get(k);
changeable = 1;
break;
}
}
if (changeable == 1)
break;
}
if (changeable == 0) {// 如果不是换乘站
newStation.setStationName(word[j]);
List<String> thisline = new ArrayList<String>();
thisline.add(linename);
newStation.setLine(thisline);
}
// 判断是否为环线，环线的第一站的站名会出现在线路的最后
if (j == length - 1 && word[j].equals(word[1])) {
// 将最后一站添加到第一站的相邻站点，将第一站添加到最后一站的相邻站点
line.get(0).addLinkStations(line.get(line.size() - 1));
line.get(line.size() - 1).addLinkStations(line.get(0));
} else {
line.add(newStation);// 将该站点添加到线路中
}
}
for (int j = 0; j < line.size(); j++) { // 处理每个车站相邻的车站
// 如果是换乘站则存在原有的相邻站点信息
List<BeanStation> newlinkStations = line.get(j).getLinkStations();
if (j != 0) {
newlinkStations.add(line.get(j - 1));
}
if (j != line.size() - 1) {
newlinkStations.add(line.get(j + 1));
}
line.get(j).setLinkStations(newlinkStations);
}
lineSet.add(line);
}
br.close();
}
private static BeanStation getnextStation() { // 选择下一个需要BFS的站点
int min = Max;// 最短经过站数，初始化为最大值
BeanStation nextStation = null;
Set
for (BeanStation s : stations) {// 遍历所有站点
if (!traveledStations.contains(s)) {// 在未BFS过的站点中选择距离最小的站点作为下一个站点
BeanRoute result = routeMap.get(s);
if (result.getDistance() < min) {
min = result.getDistance();
nextStation = result.getEndStation();
}
}
}
return nextStation;
}
// 两个站所在的相同的路线，用于判定是否换乘
private static List<String> getSameLine(BeanStation station1, BeanStation station2) {
List<String> line1 = station1.getLine();
List<String> line2 = station2.getLine();
List<String> sameline = new ArrayList<String>();
for (String i : line1) {
for (String j : line2) {
if (i.equals(j))
sameline.add(i);
}
}
return sameline;
}
public static BeanRoute BFS(BeanStation startStation, BeanStation endStation) { // BFS计算最短路径
for (List<BeanStation> l : DataProcessing.lineSet) { // 构造初始路径集
for (int i = 0; i < l.size(); i++) {// 以起始站为起点，其余所有站为终点，距离无穷大
BeanRoute result = new BeanRoute();
result.setStartStation(startStation);
result.setEndStation(l.get(i));
result.setDistance(Max);
result.setLinechange(0);
routeMap.put(l.get(i), result);// HashMap中的元素具有互异性，不需要考虑重复，若共有n个站点则有n条初始结果线路
}
}
routeMap.get(startStation).setDistance(0);
traveledStations.add(startStation);
// 初始化结果集，遍历起始站的邻居
for (BeanStation s : startStation.getLinkStations()) {
routeMap.get(s).setDistance(1);
routeMap.get(s).setLastStations(startStation);
List<String> samelines = getSameLine(startStation, s);
// 获取起始站和其邻居共同所在的路线作为Route的所在路线,如果所在的路线有多条则随机选择
routeMap.get(s).setLine(samelines.get(0));
}
BeanStation nextStation = getnextStation(); // 计算下一个站点
while (nextStation != null) { // 遍历计算每一个站点的最短路径
// 广度优先搜索
for (BeanStation s : nextStation.getLinkStations()) {
// 判断是否是最短路径，是则更新最短路径
if (routeMap.get(nextStation).getDistance() + 1 < routeMap.get(s).getDistance()) {
routeMap.get(s).setDistance(routeMap.get(nextStation).getDistance() + 1);
routeMap.get(s).setLastStations(nextStation);
List<String> samelines = getSameLine(nextStation, s);
// 判断是否需要换乘，如果nextStation的上一站和下一站没有共同所在路线，则需要换乘
if (!samelines.contains(routeMap.get(nextStation).getLine())) {
routeMap.get(s).setLine(samelines.get(0));
routeMap.get(s).setLinechange(1);
} else {
routeMap.get(s).setLine(routeMap.get(nextStation).getLine());
}
}
}
traveledStations.add(nextStation);
nextStation = getnextStation();
}
return routeMap.get(endStation);
}
6. 测试用例
起始站、目的站在同一线路上，无换乘。
环线上的两个站。
非换乘站到非换乘站
换乘站到换乘站
起始站、目的站相同
6.起始站、目的站不存在
7. 总结
这次的作业主要考察了我们关于数据结构和算法的能力，让我对BFS和Dijkstra算法有了更深入的理解。这次写博客的提交方式也很新颖。
原文：https://www.cnblogs.com/douxintong/p/13930119.html