java地铁最短距离_地铁线路最短路径问题
项目介绍
主要功能
提供一副地铁线路图，计算指定两站之间最短(最少经过站数)乘车路线；输出指定地铁线路的所有站点。以北京地铁为例，地铁线路信息保存在data.txt中，格式如下：
地铁线路总数
线路名1 站名1 站名2 站名3 ...
线路名2 站名1 站名2 站名3 ...
线路名3 站名1 站名2 站名3 ...
...
github
实现语言
java
主要算法
迪杰斯特拉(dijkstra)
类职责划分
类名
职责
Subway.java
程序的入口，处理参数和输出结果
Station.java
model，存储站点信息
result.java
model，计算最短路径时存储结果，作用类似于dist数组
DataBuilder.java
读入地铁线路图信息并存储在数据结构中
SubwayUtil.java
程序用到的算法
核心代码
public class Station {
private String name; //站点名
private List line=new ArrayList(); //所在线路(换乘站有多条)
private List linkStations = new ArrayList(); //与之相邻的站点
//这里没有放get&set和构造器的代码
}
public class Result {
private Station star; //起始站
private Station end; //终点站
private int distance; //距离
private Station passStations; //到达该站的最短路径中的上一站
private String line; //到达该站在几号线上
private int linechange; //标记从上一站到该站是否有换乘，0为无换乘，1为需换乘
//这里没有放get&set和构造器的代码
}
public class DataBuilder {
public static LinkedHashSet> lineSet = new LinkedHashSet>(); //线路集合
public DataBuilder(String pathname) throws IOException{
File filename = new File(pathname);
InputStreamReader reader = new InputStreamReader( new FileInputStream(filename));
BufferedReader br = new BufferedReader(reader);
String content="";
content=br.readLine(); //读取第一行，获取共有几条线路
int linenum=Integer.parseInt(content);
for(int i=0;i
content=br.readLine();
List line=new ArrayList();
String[] linearr=content.split(" ");
String linename=linearr[0];
for(int j=1;j
int flag=0;
for(List l:lineSet) { //处理换乘站
for(int k=0;k
if(l.get(k).getName().equals(linearr[j])) {
List newline=l.get(k).getLine();
newline.add(linename);
l.get(k).setLine(newline);
line.add(l.get(k));
flag=1;
break;
}
}
if(flag==1)
break;
}
if(j==linearr.length-1&&linearr[j].equals(linearr[1])) { //处理环线
line.get(0).getLinkStations().add(line.get(line.size()-1));
line.get(line.size()-1).getLinkStations().add(line.get(0));
flag=1;
}
if(flag==0)
line.add(new Station(linearr[j],linename));
}
for(int j=0;j
List newlinkStations=line.get(j).getLinkStations();
if(j==0) {
newlinkStations.add(line.get(j+1));
line.get(j).setLinkStations(newlinkStations);
}
else if(j==line.size()-1) {
newlinkStations.add(line.get(j-1));
line.get(j).setLinkStations(newlinkStations);
}
else {
newlinkStations.add(line.get(j+1));
newlinkStations.add(line.get(j-1));
line.get(j).setLinkStations(newlinkStations);
}
}
lineSet.add(line);
}
br.close();
}
}
public class SubwayUtil {
private static List analysisList = new ArrayList<>(); //已经分析过的站点
private static HashMap resultMap = new HashMap<>(); //结果集
private static Station getNextStation() { //获取下一个需要分析的站点
int min=999999;
Station rets = null;
Set stations = resultMap.keySet();
for (Station station : stations) {
if (analysisList.contains(station)) {
continue;
}
Result result = resultMap.get(station);
if (result.getDistance() < min) {
min = result.getDistance();
rets = result.getEnd();
}
}
return rets;
}
private static List getSameLine(List l1,List l2) { //获取l1和l2中相同的线路
List sameline=new ArrayList();
for(String la:l1) {
for(String lb:l2) {
if(la.equals(lb))
sameline.add(la);
}
}
return sameline;
}
public static Result shortestPath(Station star, Station end) { //dijkstra计算最短路径
for(List l:DataBuilder.lineSet) { //构造结果集
for(int k=0;k
Result result = new Result();
result.setStar(star);
result.setEnd(l.get(k));
result.setDistance(999999);
result.setLinechange(0);
resultMap.put(l.get(k), result);
}
}
for(Station s:star.getLinkStations()) { //初始化结果集
resultMap.get(s).setDistance(1);
resultMap.get(s).setPassStations(star);
List samelines=getSameLine(star.getLine(),s.getLine());
resultMap.get(s).setLine(samelines.get(0));
}
resultMap.get(star).setDistance(0);
analysisList.add(star);
Station nextstation = getNextStation(); //计算下一个需要分析的站点
while(nextstation!=null) { //循环计算每一个站点的最短路径
for(Station s:nextstation.getLinkStations()) {
if(resultMap.get(nextstation).getDistance()+1
resultMap.get(s).setDistance(resultMap.get(nextstation).getDistance()+1);
resultMap.get(s).setPassStations(nextstation);
List samelines=getSameLine(nextstation.getLine(),s.getLine());
if(!samelines.contains(resultMap.get(nextstation).getLine())) { //需要换乘
resultMap.get(s).setLine(samelines.get(0));
resultMap.get(s).setLinechange(1);
}
else {
resultMap.get(s).setLine(resultMap.get(nextstation).getLine());
}
}
}
analysisList.add(nextstation);
nextstation = getNextStation();
}
return resultMap.get(end);
}
public static List getLineStation(String linename){ //获取指定路线的所有站点
int flag=1;
for (List l:DataBuilder.lineSet) {
flag=1;
for(Station s :l) {
if(!s.getLine().contains(linename))
flag=0;
}
if(flag==1)
return l;
}
return null;
}
public static List getPath(Result r){ //根据result生成乘车路线
List path=new ArrayList();
Stack tmp=new Stack();
Station s=r.getPassStations();
while(!s.equals(r.getStar())) {
tmp.push(s);
s=resultMap.get(s).getPassStations();
}
path.add(r.getStar().getName());
while(!tmp.empty()) {
if(resultMap.get(tmp.peek()).getLinechange()==1) {
path.add("->换乘"+resultMap.get(tmp.peek()).getLine());
path.add(tmp.pop().getName());
}
else
path.add(tmp.pop().getName());
}
if(r.getLinechange()==1) {
path.add("->换乘"+r.getLine());
path.add(r.getEnd().getName());
}
else
path.add(r.getEnd().getName());
return path;
}
}
测试用例
获得1号线的所有站点
运行参数：-a 1号线 -map data.txt -o result.txt
输出：
苹果园 古城 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨路 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠 四惠东
获得2号线的所有站点(环线)
运行参数：-a 2号线 -map data.txt -o result.txt
输出：
西直门 积水潭 鼓楼大街 安定门 雍和宫 东直门 东四十条 朝阳门 建国门 北京站 崇文门 前门 和平门 宣武门 长椿街 复兴门 阜成门 车公庄 --该线路为环线--
从天通苑到花园桥(单线站点到单线站点)
运行参数：-b 天通苑 花园桥 -map data.txt -o result.txt
输出：
共经过16站
天通苑
天通苑南
立水桥
->换乘13号线
霍营
回龙观
龙泽
西二旗
上地
五道口
知春路
大钟寺
西直门
->换乘2号线
车公庄
->换乘6号线
车公庄西
白石桥南
花园桥
从奥林匹克公园到东直门(换乘站到换乘站)
运行参数：-b 奥林匹克公园 东直门 -map data.txt -o result.txt
输出：
共经过9站
奥林匹克公园
奥林中心
北土城
安华桥
安德里北街
鼓楼大街
->换乘2号线
安定门
雍和宫
东直门
从巴沟到长春桥(环线)
运行参数：-b 巴沟 长春桥 -map data.txt -o result.txt
输出：
共经过3站
巴沟
火器营
长春桥
异常处理
查找不存在的地铁线路
运行参数：-a 20号线 -map data.txt -o result.txt
输出：
不存在该地铁线路
输入的起始站或终点站不存在
运行参数：-b 西直门 龙翔桥 -map data.txt -o result.txt
输出：
输入的站点名不存在