北京地铁线路规划

代码仓库

https://github.com/Nevermoves/PekingSubwayInquir

需求分析

https://www.cnblogs.com/Javen003/p/11547788.html

模块分析

本项目将项目模块分为主模块、存储模块、IO模块和算法模块

主模块

• 启动程序并查询需要在命令行中输入参数指令
• 指令将通过正则表达式匹配判断

提供命令参数 -a 来获得某地铁线路上所有站点的信息，并通过参数 -o 将查询结果输入到指定文件

java subway -a 1号线 -map subway.txt -o station.txt

匹配的正则表达式

String line="-a \\S+ -map \\S+ -o \\S+ ";

提供命令参数 -b 来获得两个地铁站点之间d 最短线路，同样可通过参数 -o 将查询结果输入到指定文件

java subway -b 莲花桥 达官营 -map subway.txt -o routine.txt

匹配的正则表达式

String path="-b \\S+ \\S+ -map \\S+ -o \\S+ ";

存储模块

存储站点信息的Station类

• stationName存储站点名称
• line存储经过该站点的轨道
• coon存储在地铁线路上与该站点相临的站点

public class Station {
    
    private String stationName;
    private Set<Line>line;
    private Set<Station>conn;
    
}

存储线路信息的Line类

• lineName存储线路名称
• stations存储该线路经过的站点

public class Line {
    
    private String lineName;
    private List<Station>stations;
    
}

存储图的BuildMap类

图的存储结构

• 由于计算最短是有Dijkstra算法实现的，用数字下标代替类计算将会提高写代码的效率
• 建立多种映射关系原因同上
• 图的不同结点的连接通过Station类中的conn实现邻接表存储

public class BuildMap {

    private static Map<Integer,Station>map;   //存储站点下标对站点的映射
    
    private static Map<String,Integer>numMap; //存储站点名称对站点下标的映射
    
    private static Set<String>set;            //存储站点名称的集合
    
    private static Map<String,Line>lines;     //存储线路名称对线路的映射
    
    public static int count;                  //存储站点数
}

IO模块

xml文件读取

如果单纯只是为了实现实验需求，即简单的查询系统，其实可以选择使用txt文件存储地铁信息
但出于规范统一，以及可能的后续功能拓展的考虑，由于txt文件的局限性，我还是选择用xml文件格式来存储地铁信息

xml文件格式

整个城市的地铁线路存入root中
一条地铁线路用 Line封装，将地铁的线路名设为标签
Line内包含多个Station，用于存储该铁轨上各个站点的名称

<root>

    <Line id="1号线">

        <Station>苹果园</Station>
        <Station>古城</Station>
        <Station>八角游乐园</Station>

        <!-- more stations -->

        <Station>四惠东</Station>

    </Line>

    <!-- more lines -->
</root>

xml文件读取

• 通过ReadLIne类实现xml文件的读取
• 读取方式使用了dom框架
• 将每条线路都存储在List<String>中，其中第一项为线路名名称，其余皆为站点名称
• 所有的线路都存储在set中

public class ReadLine {
    
    private static Set<List<String>>set;
    
    public ReadLine(String fileName) throws Exception {
        
        File file=new File(fileName);
        
        if(!file.exists()) {
            System.out.println("文件"+fileName+"不存在.");
            System.exit(0);
        }
        set=new HashSet<List<String>>();

        DocumentBuilder documentBuilder=DocumentBuilderFactory.newInstance().newDocumentBuilder();
        Document document=documentBuilder.parse(file);
        Element root=document.getDocumentElement();
        NodeList lineList=root.getElementsByTagName("Line");
        
        for(int i=0;i<lineList.getLength();i++) {
            
            Node liNode=lineList.item(i);
            Element element=(Element) liNode;
            NodeList stationList=element.getElementsByTagName("Station");
            List<String>stations=new ArrayList<String>();
            
            NamedNodeMap nameNodeMap=liNode.getAttributes();
            String id=nameNodeMap.getNamedItem("id").getTextContent();
            stations.add(id);
            
            for(int j=0;j<stationList.getLength();j++) {
                
                stations.add(stationList.item(j).getTextContent());
            }
            
            set.add(stations);
        }
    }
}

线路查询结果存储

线路查询的结果输出文件格式

八通线
四惠
四惠东
高碑店
...

路径查询结果存储

路径查询的结果输出文件格式

5
10号线
莲花桥
六里桥

9号线
六里桥
六里桥东
...
达官营

算法模块

算法模块中主要有四个方法，分别为图的初始化，Dijkstra算法，导出并寻找最优路径

Dijkstra类说明

public class Dijkstra {
    
    private int inf;                       //假象无穷大数 
    private int len;                       //存储站点数
    private int startId;                   //存储起点的下标
    private int endId;                     //存储终点的下标

    private int[] dis;                     //存储所有结点到起点的距离
    private int[] vis;                     //存储所有被访问情况
    private Map<Integer,Set<Integer>>from; //存储起点到所有结点的最短路径的所有前置结点
    
    private List<Line>bestPath;            //存储最优路径
    private List<Integer>path;             //存储当前路径
}

图的初始化

• 图的初始化由方法init实现
• 方法的主要功能为数据的初始化，以及对起点及其周围的点预处理
• 根据起点和终点的站点名称，确定起点和终点的下标，若无该站点或是起点与终点相同，则提示并终止程序的运行

    private void init(String start,String end) {
        if(start.equals(end)) {
            System.out.println("别浪费钱啊！");
            System.exit(0);
        }
        inf=Integer.MAX_VALUE;
        
        bestPath=null;
        path=new ArrayList<Integer>();
        
        len=BuildMap.getMap().size();
        

        if(BuildMap.getNumMap().containsKey(start)) {
            startId=BuildMap.getNumMap().get(start);
        }
        else {
            System.out.println("站点 "+start+" 不存在");
            System.exit(0);
        }
        if(BuildMap.getNumMap().containsKey(end)) {
            endId=BuildMap.getNumMap().get(end);
        }
        else {
            System.out.println("站点 "+end+" 不存在");
            System.exit(0);
        }
        
        from=new HashMap<Integer, Set<Integer>>();
        
        dis=new int[len];
        vis=new int[len];
        
        for(int i=0;i<len;i++) {
            
            Set set=new HashSet<Integer>();
            from.put(i,set);
            vis[i]=0;
            dis[i]=inf;     
        }   

        dis[startId]=0;
        vis[startId]=1;
        
        Station station=BuildMap.getMap().get(startId);
        
        for(Station s:station.getConn()) {
            
            int conn=BuildMap.getNumMap().get(s.getStationName());
            dis[conn]=1;
            from.get(conn).add(startId);    
        }
    }

Dijkstra算法

• Dijkstra算法的主要功能为计算各个结点到起点的最短距离
• 时间复杂度O(N+V) ,空间复杂度为O(N+V)
• 算法实现为每次循环寻找与起点距离最近、距离被更新且未被访问的结点，更新与其相邻的结点到起点的距离，直至找不到为止
• 每次结点A更新了结点B的距离时判断，若结点B新距离小于更新前到起点的距离，则清空from[B]，并将A加入from[B]
• 若结点B新距离与更新前到起点的距离相同，则将A加入from[B]中，使A成为B的最短路径的前置结点之一，以此得到多条最短路径

    private void dijkstra() {
    
        while(true) {
            
            int x=-1;
            int minx=inf;
            
            for(int i=0;i<len;i++) {
                
                if(vis[i]==1||dis[i]==inf)continue;
                
                if(dis[i]<minx) {
                    
                    minx=dis[i];
                    x=i;
                }
            }
            
            if(x==-1)break;
            
            vis[x]=1;
            for(Station stationy : BuildMap.getMap().get(x).getConn()) {
                
                int y=BuildMap.getNumMap().get(stationy.getStationName());
                
                if(vis[y]==1)continue;
                
                if(dis[x]+1==dis[y]) {
                    
                    from.get(y).clear();
                    from.get(y).add(x);             
                }
                else if(dis[x]+1<dis[y]) {
                    
                    dis[y]=dis[x]+1;
                    from.get(y).add(x);
                }
            }   
        }
    }

寻找最优路径

• 寻找最优路径的功能由两个方法共同实现
• 方法getPath的功能为将由路径的站点下标组成的List<Integer>转化为站点和线路List<Line>
• 方法buildPath为遍历所有的最短路径，存入List后输入方法getPath得到路径，筛选出换成次数最少的路径，最后输出结果

    public void buildPath(int now) {
        
        path.add(0,now);
        
        if(now==startId) {
            
            List<Line>nowPath=BuildMap.getPath(path);
            
            if(bestPath==null) bestPath=nowPath;
            else {
                
                if(nowPath.size()<bestPath.size()) bestPath=nowPath;
            }
        }
        else {
            
            for(int last:from.get(now)) {
                
                buildPath(last);
            }
        }
        path.remove(0);
    }
    public static List<Line> getPath(List<Integer> pathIndex){

        List<Line>path=new ArrayList<Line>();
        
        int len=pathIndex.size();
            
        Station laStation=map.get(pathIndex.get(0));
        Station noStation=map.get(pathIndex.get(1));
            
        Line laLine=null;
            
        for(int i=0;i<len;i++) {
            
            if(i==0||(!noStation.getLine().contains(lines.get(laLine.getLineName())))) {
                
                for(Line l:laStation.getLine()) {
                    
                    if(noStation.getLine().contains(l)) {
                        
                        laLine=new Line(l.getLineName());
                        laLine.addStation(laStation);
                            if(i!=0)laLine.addStation(noStation);
                        
                        path.add(laLine);
                        break;
                    }
                }
            }
            else {
                
                laLine.addStation(noStation);           
            }
            
            laStation=noStation;
            if(i<len-1)noStation=map.get(pathIndex.get(i+1));
        }

        return path;
    }

北京地铁线路规划

原文：https://www.cnblogs.com/Javen003/p/11668357.html