个人项目——地铁线路规划
读取地铁线路txt文本
public static void readSubway() { File file = new File(FILE_PATH); BufferedReader reader = null; try { InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(file),"UTF-8"); reader = new BufferedReader(inputStreamReader); String line = null; String lineName = "001"; distanceMap.put("001",new HashMap<>()); while ((line = reader.readLine()) != null) { if(line.trim().length()==1||line.trim().length()==3||line.trim().length()==2){ if(line.trim().length()==3||line.trim().length()==2){ // \uFEFF 默认以这个开头!!! continue; } lineName = line; if(!distanceMap.keySet().contains(line)){ distanceMap.put(line.trim(),new HashMap<>()); } }else{ if(line.trim().startsWith("*")){ String[] lineInfo = line.substring(1).split("-"); lineSet.add(getLine(lineInfo[1].trim(),lineInfo[0].trim())); }else{ String texts[] = line.split("\t"); String key = texts[0].trim(); Double value = Double.valueOf(texts[1]); distanceMap.get(lineName).put(key,value); String other = key.split(":")[1].trim()+":"+key.split(":")[0].trim(); distanceMap.get(lineName).put(other,value); } } } } catch (UnsupportedEncodingException e) { e.printStackTrace(); } catch (FileNotFoundException e) { e.printStackTrace(); }catch (IOException e) { e.printStackTrace(); } finally { } }
选择起点站与终点站的最短路径
public static Result calculate(Station star, Station end) { if (!analysisList.contains(star)) { analysisList.add(star); }//将star站点放到以及分析的站点中去 if (star.equals(end)) { Result result = new Result(); result.setDistance(0.0D); result.setEndStation(star); result.setStarStation(star); return resultMap.put(star, result); }//当star站点等于end站点,则设置result的距离为0,end站点为star站点。 if (resultMap.isEmpty()) { //当第一次调用calculate,并且起始点和终止点不同,那么resultMap为空。 List<Station> linkStations = getLinkStations(star); //把相邻站点集合中的所有站点,加入resultMap中。 for (Station station : linkStations) { Result result = new Result(); result.setStarStation(star); result.setEndStation(station); String key = star.getName() + ":" + station.getName(); Double distance = Builder.getDistance(key); result.setDistance(distance); result.getPassStation().add(station); resultMap.put(station, result); } } Station parent = getNextStation(); if (parent == null) {//如果resultMap所有点keySet被分析完了,则返回的parent为null。 Result result = new Result(); result.setDistance(0.0D); result.setStarStation(star); result.setEndStation(end); //put方法的返回值就是value值。 return resultMap.put(end, result); } //如果得到的最佳邻点与目标点相同,则直接返回最佳邻点对应的result对象。 if (parent.equals(end)) { return resultMap.get(parent); } //在路径经过点中加入parent后,更新resultMap集合,要么起始点经过parent达到parent相邻点是最优的,要么起始点到parent相邻点不可达,而通过parent可达。 //获取parent对象(最佳点)的相邻点。 //分析一个parent最佳点后,把它的相邻点都会加入到resultMap中,在下一次调用getNextStation获取resultMap中未被标记且距离(起始点到该station的距离)最短。 List<Station> childLinkStations = getLinkStations(parent); for (Station child : childLinkStations) { if (analysisList.contains(child)) { continue; } String key = parent.getName() + ":" + child.getName(); Double distance; distance = Builder.getDistance(key); Builder.getDistance(key); if (parent.getName().equals(child.getName())) { distance = 0.0D; } Double parentDistance = resultMap.get(parent).getDistance(); distance = doubleAdd(distance,parentDistance); List<Station> parentPassStations = resultMap.get(parent).getPassStation(); Result childResult = resultMap.get(child); if (childResult != null) { if (childResult.getDistance() > distance) { //如果通过最佳点比直接到距离小,则更新resultMap中的对应result对象。 childResult.setDistance(distance); childResult.getPassStation().clear(); childResult.getPassStation().addAll(parentPassStations); childResult.getPassStation().add(child);//路径更新为A->最佳点->child点。 } } else { //如果在resultMap中没有最佳点的相邻点,则往resultMap中添加通过最佳点(初始为起始点的最佳邻点)到达该点。 childResult = new Result(); childResult.setDistance(distance); childResult.setStarStation(star); childResult.setEndStation(child); childResult.getPassStation().addAll(parentPassStations); childResult.getPassStation().add(child); } resultMap.put(child, childResult); } analysisList.add(parent); calculate(star, end); return resultMap.get(end); }
读取相邻站点
public static List<Station> getLinkStations(Station station) { List<Station> linkedStaions = new ArrayList<Station>(); for (List<Station> line : Builder.lineSet) {//遍历每条地铁线 for (int i = 0; i < line.size(); i++) { if (station.equals(line.get(i))) { if (i == 0) { //如果该站点位于地铁线的起始站,则相邻站为地铁线的第二个站点(i+1), linkedStaions.add(line.get(i + 1)); } else if (i == (line.size() - 1)) {//如果该站点位于地铁线的最后一个站,则相邻站为地铁线的倒数第二个站点(i-1), linkedStaions.add(line.get(i - 1)); } else { //如果该站点位于地铁线的其余位置,则相邻站点为该站点前后位置(i-1/i+1) linkedStaions.add(line.get(i + 1)); linkedStaions.add(line.get(i - 1)); } } } } return linkedStaions; }
读取下一个站点
private static Station getNextStation() { Double min = Double.MAX_VALUE; Station rets = null; Set<Station> stations = resultMap.keySet();//获取resultMap中的station集合 for (Station station : stations) { if (analysisList.contains(station)) {//如果该点被标记为“已被分析”,则跳过分析 continue; } //循环比较resultMap中未被标记的点,求出最短路径的result对象。 Result result = resultMap.get(station); if (result.getDistance() < min) { min = result.getDistance(); rets = result.getEndStation(); } } return rets;//返回下一个站点 }
获取地铁线路名称
public static String getLineNameByStation(Station station){ Create(); String startname = station.getName(); for (Map.Entry<String,List<Station>> entry : lineData.entrySet()) { List<Station> stations = entry.getValue(); for (Station sta : stations){ if(sta.getName().equals(startname)){ return entry.getKey(); } } } return ""; }
获取经过站点名称
public static void getPassStation(Result result){ Station starStation = result.getStarStation(); Station endStation = result.getEndStation(); String starLine = getLineNameByStation(starStation); String converLine = starLine; System.out.println("起始地铁线:"+starLine); System.out.print(starStation.getName()+"->"); for (Station station : result.getPassStation()) { if(!converLine.equals(station.getLine())){ System.out.print("(换乘地铁线:"+station.getLine()+")"); converLine = station.getLine(); } if(endStation.getName()!=station.getName()) System.out.print(station.getName() + "->"); else if(endStation.getName()==station.getName()) System.out.print(station.getName()); } }
输出信息
public static void write() { input = new Scanner(System.in); Builder.readSubway(); System.out.println("指令1格式(查询地铁线路信息:-a 001号线)"); System.out.println("指令2格式(查询起末站线路:-b 苹果园 玉泉路)"); System.out.print("输入指令:"); String s=input.nextLine(); String[] split =s.split("\\s+"); switch(split[0]) { case "-a": if(split.length==2){ Builder.getLineDate(split[1]); System.out.println(); }else{ System.out.println("输入错误,请重新输入!"); System.out.println(); } break; case "-b": if(split.length==3){ if(split[1].equals(split[2])) { System.out.println("起始站和终点站相同,请重新输入!"); } else { Result result = Dijkstra.calculate(new Station(split[1]), new Station(split[2])); Builder.getPassStation(result); System.out.println(); } }else{ System.out.println("输入错误,请重新输入!"); System.out.println(); } break; default: System.out.println("输入格式错误,请重新输入!"); System.out.println(); break; } }
测试指令
测试指令1:
测试指令2:
测试3:输入起点站和终点站相同
测试4:输入格式1错误
测试5:输入格式2错误
测试6:输入格式3错误
但是,虽然可以发现输入参数的个数不对,但无法发现在输入参数个数符合要求时,输入的参数不符合规范时发现错误。
github链接:https://github.com/Three666/subway