个人项目--北京地铁线路规划

北京地铁线路图

需求分析：

通过文本输入地铁线路信息
线路查询功能北京地铁
任意站点之间最短路径的查询

实现过程：

地铁图输入格式

　　本次实验的线路采用txt文件输入，每两行代表一条线路。其中第一行表示线路名称，第二行表示包含在此线路上的所有站点的名称。

结果输出：

　　本次实验的查询输出结果将由GUI所绘制的界面来显示。输入线路名称或起点、终点信息即可返回要求的线路信息和最短路径信息。

算法设计

　　本次实验是通过Floyd算法来得到两站点之间的最短路径。首先定义了Graph类，用于建立邻接矩阵，初始化地铁路线图。

public class Graph {
    
    private int[][] distance=new int[500][500];
    private int MaxSize;
    private List<Station> allStations= new ArrayList<Station>();
    //用于保存所有的站点信息
    
    
        
    public void InitGraph(List<SubwayLine> allLines) {
        
        for(int i=0;i<allLines.size();i++) {
            List<Station> Stations=allLines.get(i).getSubwayStation();
            for(int j=0;j<Stations.size();j++) {
                //查询该站点是否已存在
                int index=this.getIndex(Stations.get(j));
                if(index==-1)
                    allStations.add(Stations.get(j));
                else if(index!=-1) {
                    //站点多次出现，表示该站为换乘站
                    allStations.get(index).setChangeStation(true);
                    allLines.get(i).getSubwayStation().get(j).setChangeStation(true);
                }
            }    
        }
        
        
        MaxSize=allStations.size();
        
        //初始化邻接矩阵
        for(int i=0;i<MaxSize;i++)
            for(int j=0;j<MaxSize;j++){
                if(i==j)
                distance[i][j]=0;
                else
                distance[i][j]=500;
            }        
        //遍历所有线路,设置站点可达
        for(SubwayLine line:allLines) {
            List<Station> Stations=line.getSubwayStation();
            for(int j=0;j<Stations.size()-1;j++) {
                int start =this.getIndex(Stations.get(j));
                int end =this.getIndex(Stations.get(j+1));    
                distance[start][end]=1;
                distance[end][start]=1;
            }    
        }
        
        
    }
    
    
    public int getIndex(Station s) {    
        for(int i=0;i<allStations.size();i++)
            if(allStations.get(i).getName().equals(s.getName()))
                return i;    
        return -1;
    }

    public int findStation(String name) {
        for(int i=0;i<allStations.size();i++)
            if(allStations.get(i).getName().equals(name))
                return i;    
        return -1;
    }
    
    public int[][] getDistance() {
        return distance;
    }

    public void setDistance(int[][] distance) {
        this.distance = distance;
    }

    public int getMaxSize() {
        return MaxSize;
    }

    public void setMaxSize(int maxSize) {
        MaxSize = maxSize;
    }

    public List<Station> getAllStations() {
        return allStations;
    }

    public void setAllStations(List<Station> allStations) {
        this.allStations = allStations;
    }
}

　　通过对图的邻接矩阵和所有站点的信息的处理，得到最短路径并输出结果

//s1为起点的名称,s2为终点的名称,G为初始化的图,allLines为所有地铁线路的集合
    public ArrayList<String> findMin(String s1,String s2,Graph G,List<SubwayLine> allLines) throws Exception {
        int size=G.getMaxSize();
        //记录任意两点路径的邻接矩阵
        int[][] path=new int[size][size];
        
        int[][] d=G.getDistance();
            
        for(int i=0;i<size;i++)
            for(int j=0;j<size;j++){
                path[i][j]=j;
        }
        //Floyd算法        
        for(int k=0; k<size; k++){
            for(int i=0; i<size; i++){
                for(int j=0; j<size; j++) {
                    if(d[i][k]!=-1&&d[k][j]!=-1) {
                        //如果存在中间站点k使得从站点i到站点j的距离更短，将站点k加入到路径中，更新距离
                        if(d[i][j]>d[i][k]+d[k][j]) {
                            d[i][j]=d[i][k]+d[k][j];
                            path[i][j]=path[i][k];
                        }    
                    }
                }
            }
        }
        
        int start=G.findStation(s1);
        int end=G.findStation(s2);        
        if(start==-1)
            throw new Exception("起点不存在");
        if(end==-1)
            throw new Exception("终点不存在");    
        if(start==end)
            throw new Exception("起点和终点不能相同");
        
        //outList为记录最短路径通过的站点的集合
        //记录最终的最短路径的结果
        ArrayList<String> result=new ArrayList<String>();
        
        if(start!=-1&&end!=-1) {
            int count=0;
            int temp=path[start][end];
            //加入起点
            outList.add(G.getAllStations().get(start));
            while(temp!=end ) {
                //加入中间站点直到到达终点
                outList.add(G.getAllStations().get(temp));
                temp=path[temp][end];
            }
            //加入终点
            outList.add(G.getAllStations().get(temp));
            
            result.add(Integer.toString(outList.size()));    
            result.add(outList.get(0).getName());    
            for(int i=1;i<outList.size()-1;i++) {    
                result.add(outList.get(i).getName());
                //判断该站点是否为换乘站,若为换乘站则调用函数IsChangeLine判断是否在该站换乘
                if(outList.get(i).isChangeStation()==true) {
                    String res=IsChangeLine(outList.get(i-1).getName(),outList.get(i).getName(),outList.get(i+1).getName(),allLines);
                    if(res!=null)
                        result.add(res);
                        
                }
            }    
            result.add(outList.get(outList.size()-1).getName());
            
        }
        
        return result;
        
    }

public  SubwayLine PrintLine(String name,List<SubwayLine> allLines) {
        //根据线路名遍历线路集合返回对应的线路信息
        for(SubwayLine s:allLines) {
            if(name.equals(s.getName())) {
                return s;
            }        
        }
        return null;
    }

//pre为当前站点的前一站,mid为当前站点,next为当前站点的下一站, allLines为所有线路的集合
    public String IsChangeLine(String pre,String mid,String next,List<SubwayLine> allLines) {
        String start=null;
        String end=null;
        for(SubwayLine s:allLines) {
            //调用HaveStation函数根据当前站和前一站来确定当前线路的名称
            if(s.HaveStation(pre)&&s.HaveStation(mid))
                start=s.getName();
            ////调用HaveStation函数根据当前站和下一站来确定接下来的线路名称
            if(s.HaveStation(mid)&&s.HaveStation(next))
                end=s.getName();
        }
        //如果不同则发生换乘,返回换乘线路
        if(!start.equals(end))
            return end;
            
        return null;
    }