地铁线路最短路径(完整版)

2023-09-23 10:11:27

1.主要功能

提供一副地铁线路图(以北京地铁为例)
——计算指定两站之间最短（最少经过站数）乘车路线
——输出指定地铁线路的所有站点

地铁线路信息保存在data.txt中，格式如下：

线路名1 站名1 站名2 站名3...
线路名2 站名1 站名2 站名3...
线路名3 站名1 站名2 站名3...

2.实现语言

Java语言

3.实现算法

Dijkstra算法

4.类职责划分

类	职责
main	代码交互和读取部分
method	存放了迪杰斯特拉算法函数，输出站点函数，检验函数等

5.核心代码

以下为简化代码，完整代码已经上传至Github

1.数据的存储

　static Map<String, Integer> stationflag=new HashMap<String, Integer>();//存放站点和站点的标记
   static Map<String, String> stationline=new HashMap<String,String>();//存放站点和地铁线名称

2.数据的读入

try {
            //读取文件
            String filePath="C:\\Users\\18418\\Desktop\\地铁线路信息.txt";
            File file=new File(filePath);
            InputStreamReader read=new InputStreamReader(new FileInputStream(file),"UTF-8"); 
            BufferedReader br=new BufferedReader(read);
            String lineTxt=null;
        while ((lineTxt=br.readLine())!=null) {
            String na=null;
            String[] arr=lineTxt.split(" ");//取出语句的空格后存放到'arr'数组
            //取出地铁线名字并且删除
            String linename=arr[0];
            for(int i=0;i<arr.length-1;i++)
                arr[i]=arr[i+1];
            for (String namer : arr){                        
                if (stationflag.keySet().contains(namer)) { //map包含的键的set视图中是否包含已经包含了该站点
                    int temp=0;
                    for(int i=0;i<arr.length;i++) {
                        if(namer.equals(arr[i])) 
                            temp++;
                        }
                    if(temp==1){
                        stationflag.put(namer,(stationflag.get(namer)+1));
                        stationline.put(namer,stationline.get(namer)+","+linename);
                    }
                }
                else {//否则新存入一个站点信息
                    name[x]=namer;
                    x++;
                    stationflag.put(namer,1);
                    stationline.put(namer,linename);
                }
                if(na!=null) {
                    Map[n*list.indexOf(namer)+list.indexOf(na)]=2;
                    Map[n*list.indexOf(na)+list.indexOf(namer)]=2;    
                }
                na=namer;
            }
        }
        br.close();
        }catch (Exception e) {
            System.out.println("找不到指定的文件");
        }

3.迪杰斯特拉算法实现

public double Dijkstra(double Map[],int path[],int n,int m,int d) {
        int u,t;
        double min,result;
        double dist[]=new double[n+1];
        int s[]=new int[n+1];
        for(int i=0;i<n;i++){
            dist[i]=Map[n*m+i];
            s[i]=0;
            if(i!=m&&dist[i]<Over){
                path[i]=m;
            }
            else
                path[i]=-1;
        }
        s[m]=1;
        for(int i=0;i<n-1;i++){
            min=Over;
            u=m;
            for(int j=0;j<n;j++){
                if (s[j]==0&&dist[j]<min){
                    u=j;
                    min=dist[j];
                }
            }
            s[u]=1;
            for(t=0;t<n;t++){
                if (s[t]==0&&dist[u]+Map[n*u+t]<dist[t]) {
                    dist[t]=(float)(dist[u]+Map[n*u+t]);
                    path[t]=u;
                }
            }
        }
        result=dist[d];
        return result;
    }

4.检测站点是否存在

    //判断站点是否存在
    public static boolean exist(String name[],String nam,int n) {
        int i=0;
        while (i<n) {
            if (name[i]!=null&&name[i].equals(nam)) { //判断站点存在其中，则返回true
                return true;
            }
            i++;
        }
        return false;
    }

5.输出函数

　　//输出站点
    public void print(int pa[],String nam[],int d,int i)
    {
        if (pa[i]>=0) { 
            print(pa,nam,d,pa[i]);
            System.out.print("——>" +nam[pa[i]]); //输出的格式
        }
    }

6.主函数交互

Scanner scanf=new Scanner(System.in);
        
        System.out.print("请输入起点站名:");
        start = scanf.nextLine();
        while (!e.exist(name, start, n)) {
            System.out.println("站点输入错误！");
            System.out.print("请重新输入起点站名:");
            start = scanf.nextLine();
        }
        System.out.print("请输入终点站名:");
        dest = scanf.nextLine();
        while (!e.exist(name, dest, n)) {
            System.out.println("站点输入错误！");
            System.out.print("请重新输入终点站名:");
            dest = scanf.nextLine();
        }
        
        if(e.exist(name,dest,n)) {
            method f=new method();
            float distan=(float)f.Dijkstra(Ma,pa,n,f.exam(nam,start,n), f.exam(nam,dest,n));//调用迪杰斯特拉算法查出此结点到其他点最短路径
            int s, d;
            //调用方法检测
            s=f.exam(nam,start,n);
            d=f.exam(nam,dest,n);
            System.out.print("最佳乘地铁路线：");
            //调用方法输出
            f.print(pa,nam,s,d);
            System.out.print("——>"+dest);
        }

6.测试用例

1.起点站或终点站错误(即不存在)

2.非换乘的正常执行

3.换乘站点正常执行

7.总结

一方面，通过这次的作业，我深刻认识到代码能力的欠缺，不能够灵活的运用知识解决问题。
另一方面，通过使用博客园写作业，对于简述和分析自己的代码能力有了进一步的提高。

码农公寓