个人项目——北京地铁出行线路规划

时间：2019-10-14 22:58:47 阅读：185 评论：0 收藏：0 [点我收藏+]

技术分享图片

基本需求
    1.获取所以的站点信息
    2.获取北京地铁单条线路上的所以站点
    3.获取两个站点之间的最短路线

代码简析

数据导入：

public static void read(){
	    	DistanceBuilder.FILE_PATH=System.getProperty("user.dir") + File.separator + "\\" +"subway.txt";
	    	DistanceBuilder.readSubway();
	    }

读取地铁线路信息：

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如：苹果园:古城   double为距离，如：1
            //默认起始为1号线
            String lineName = "1";
            distanceMap.put("1",new HashMap<>());
            while ((line = reader.readLine()) != null) {
                //长度为1或2，则该行值为地铁线号。
                if(line.trim().length()==1||line.trim().length()==3||line.trim().length()==2){
                    if(line.trim().length()==3||line.trim().length()==2){ 
                        continue;
                    }
                    lineName = line;
                    //判断distanceMap中是否已创建该地铁线号。如果为创建该地铁线则加入distanceMap
                    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{
                        //地铁某站点到某站点信息，如:苹果园:古城	1
                        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 class DijkstraUtil {
    private static HashMap<Station, Result> resultMap = new HashMap<>();   // 分析过的站点集合.     
    private static List<Station> analysisList = new ArrayList<>();

    public static Result calculate(Station star, Station end) {   //迪杰斯特拉算法应用在地铁的实现.
        if (!analysisList.contains(star)) {
            analysisList.add(star);
        }
        if (star.equals(end)) {//起始站和终点站相同时返回result=0，终点站就是初始站
            Result result = new Result();
            result.setDistance(0.0D);
            result.setEnd(star);
            result.setStar(star);
            return resultMap.put(star, result);
            
        }
        if (resultMap.isEmpty()) {    //第一次调用calculate，且起始点和终止点不同，则resultMap为空。
            List<Station> linkStations = getLinkStations(star);   //第一次调用获取起始点的相邻站点（在所有地铁线中，这里涉及转线交叉的周围站点）
            for (Station station : linkStations) {   //把相邻站点集合中的所有站点，加入resultMap中，可以直接获取Distance。
                Result result = new Result();
                result.setStar(star);
                result.setEnd(station);
                String key = star.getName() + ":" + station.getName();
                Double distance = DistanceBuilder.getDistance(key);
                result.setDistance(distance);
                result.getPassStations().add(station);
                resultMap.put(station, result);
            }
        }
        Station parent = getNextStation();
        if (parent == null) {    //返回的parent为null，说明resultMap所有点keySet被分析完了
            Result result = new Result();
            result.setDistance(0.0D);
            result.setStar(star);
            result.setEnd(end);
            return resultMap.put(end, result);
        }
        if (parent.equals(end)) {   //寻找到终点，直接返回对应的result
            return resultMap.get(parent);
        }
        List<Station> childLinkStations = getLinkStations(parent);
        for (Station child : childLinkStations) {
            if (analysisList.contains(child)) {
                continue;
            }
            String key = parent.getName() + ":" + child.getName();
            Double distance;
            distance = DistanceBuilder.getDistance(key);
            DistanceBuilder.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).getPassStations();
            Result childResult = resultMap.get(child);
            if (childResult != null) {
                if (childResult.getDistance() > distance) {     //通过最佳点比直接到距离小，就更新resultMap中的对应result对象。
                    childResult.setDistance(distance);
                    childResult.getPassStations().clear();
                    childResult.getPassStations().addAll(parentPassStations);//路线更新
                    childResult.getPassStations().add(child);
                }
            } else {   //通过最佳点比直接到距离小，直接从原路线到child点
                childResult = new Result();
                childResult.setDistance(distance);
                childResult.setStar(star);
                childResult.setEnd(child);
                childResult.getPassStations().addAll(parentPassStations);
                childResult.getPassStations().add(child);
            }
            resultMap.put(child, childResult);
        }
        analysisList.add(parent);
        calculate(star, end);
        return resultMap.get(end);
        
    }

　　地铁线路切换以及相邻节点遍历：

private static List<Station> getLinkStations(Station station) {  // 获取所有相邻节点.
        List<Station> linkedStaions = new ArrayList<Station>();
        for (List<Station> line : DistanceBuilder.lineSet) {    //遍历所有地铁线
            for (int i = 0; i < line.size(); i++) {
                if (station.equals(line.get(i))) {
                    if (i == 0) {
                        linkedStaions.add(line.get(i + 1));//地铁站为换乘线的初始站，则继续+1遍历
                    } else if (i == (line.size() - 1)) {
                        linkedStaions.add(line.get(i - 1));//地铁站为换乘线的终点站，则继续-1遍历
                    } else {                               //地铁站为换乘线的中途站，则继续+1，-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();
        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;
    }

　　查询该站点所在地铁线：

public static String getLineNameByStation(Station station){
        createlineData();
        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 writeLineData(String lineName){
        createlineData();
        lineName = lineName.substring(0,3);
        List<Station> lineInfo = lineData.get(lineName);
        //System.out.println(lineData.get(lineName));
        String lineStr = lineInfo.stream().map(x->x.getName()).collect(Collectors.joining(",","[","]"));
        System.out.print(lineStr);
    }

　　输出最佳路线：

public static void getPassStation(Result result){
    	//System.out.print(result.getStar());
        String starLine = getLineNameByStation(result.getStar());
        String converLine = starLine;
        System.out.println("起始地铁线："+starLine);
        for (Station station : result.getPassStations()) {
            if(!converLine.equals(station.getLine())){
                System.out.print("换乘地铁线："+station.getLine()+"  ");
                converLine = station.getLine();
                converLine = station.getLine();
            }
            System.out.print(station.getName() + " > ");
        }
    }

　　站点存储：

public class Station {
  
    private String name;  
    private String line;
    private List<Station> linkStations = new ArrayList<>();
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getLine() {
        return line;
    }
    public void setLine(String line) {
        this.line = line;
    }
    public List<Station> getLinkStations() {
        return linkStations;
    }
    public void setLinkStations(List<Station> linkStations) {
        this.linkStations = linkStations;
    }
    public Station(String name, String line) {
        this.name = name;
        this.line = line;
    }
    public Station(String name) {
        this.name = name;
    }
    public Station (){

    }
    public int hashCode() {
		return this.getName().hashCode();
	}
	public String toString() {
		return "Station{" + "name=‘" + name +‘\‘‘ +",line=‘" + line + ‘\‘‘ + ", linkStations=" + linkStations + ‘}‘;
	}
    public boolean equals(Object obj) {
        if(this == obj){
            return true;
        } else if(obj instanceof Station){
            Station s = (Station) obj;
            if(s.getName().equals(this.getName())){
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
}

　　运行结果存储：

public class Result {
    private Station star;
    private Station end;
    private Double distance = 0.0D;
    private List<Station> passStations = new ArrayList<>();
    public Station getStar() {
        return star;
    }
    public void setStar(Station star) {
        this.star = star;
    }
    public Station getEnd() {
        return end;
    }
    public void setEnd(Station end) {
        this.end = end;
    }
    public Double getDistance() {
        return distance;
    }
    public void setDistance(Double distance) {
        this.distance = distance;
    }
    public List<Station> getPassStations() {
        return passStations;
    }
    public void setPassStations(List<Station> passStations) {
        this.passStations = passStations;
    }
    public Result(Station star, Station end, Double distance) {
        this.star = star;
        this.end = end;
        this.distance = distance;
    }
    public Result() {

    }

    @Override
    public String toString() {
        return "Result{" +
                "star=" + star +
                ", end=" + end +
                ", distance=" + distance +
                ", passStations=" + passStations +
                ‘}‘;
    }
}

　　主函数：

public class Main {
	 public static void main(String[] args) {
	        read();
	        System.out.println("北京地铁查询");
	      while(true) {
	        write();
	        }
	    }
	    public static void read(){
	    	DistanceBuilder.FILE_PATH=System.getProperty("user.dir") + File.separator + "\\" +"subway.txt";
	    	DistanceBuilder.readSubway();
	    }
	    public static void write() {
	    	Scanner input=new Scanner(System.in);
	    	System.out.print("输入指令：(查询地铁线路信息：-info 八通线）,（查询起末站线路：-way star end）:");
	         String s=input.nextLine();
	         String[] split =s.split("\\s+");
	         if(split[0].equals("-map")) {
	        	 if(split.length==1){
	        		 DistanceBuilder.readSubway();
	                   System.out.println("成功读取subway.txt文件");
	               }else{
	                   System.out.println("重新输入");
	               }
	         }
	         else if(split[0].equals("-info")) {
	              if(split.length==2){
	            	  DistanceBuilder.readSubway();
	            	  DistanceBuilder.writeLineData(split[1]);
	               }else{

	                   System.out.println("输入错误，请重新输入");
	               }
	         }
	         else if(split[0].equals("-way")) {
	               if(split.length==3){
	            	   if(split[1].equals(split[2]))
	            		   System.out.println("输入站点重复，请重新输入");
	            	   else {
	            	   DistanceBuilder.readSubway();
	            	   System.out.println(split[1]+" -> "+split[2]+":");
	                   Result result = DijkstraUtil.calculate(new Station(split[1]), new Station(split[2]));
	                   //System.out.println(split[2]);
	                   DistanceBuilder.getPassStation(result);
	                   //System.out.println(result);
	                   if(result.getDistance()==0.0)
	                	   System.out.println("输入站点不存在");
	               }
	               }else{
	                   System.out.println("输入错误，请重新输入");
	               }
	               
	         
	         }
		    	System.out.println();
	    }
}

运行结果测试

1、输出指定线路所有站点信息