V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
337136897
V2EX  ›  程序员

关于一个地图上从起点到终点找一条最短路径,该如何设计程序把路径记录下来?

  •  
  •   337136897 · 2018-11-27 15:08:14 +08:00 · 1152 次点击
    这是一个创建于 1948 天前的主题,其中的信息可能已经有所发展或是发生改变。

    近期有个这样的需求找了点东西试试水,于是找来了下面一张图

    1

    拿到这样的图后,把地区用拼音写上。然后第一列作为图的顶点,第(n%2==0,n>1)列作为这个顶点到其他地区的地点,第(n%2!=0,n>1)列作第 1 列和这个顶点的距离,就当成权重吧,自己估量的。费了不少功夫写完后生成一个邻接矩阵。

    2

    3

    现在问题来了,如果我不用地理坐标判断的话,用权重找最短路径,我要从广州到哈尔滨。它就会从广州->深圳->福州-> ....... ->哈尔滨。反而绕了远路,正常应该是从广州->衡阳->长沙这条路线走的。用深度搜索的话直接绕了整个中国才找到目的地。然而路径还是不知道该怎么记录下来,用广度的话也应该如何把每一条走过的路径记录下来,嗯最主要还是这个问题。画个图说明下:

    3

    还是想知道怎样记录这样的全部路径,然后作比较,求帮个忙出个思路和技巧,或者帮忙写一下也行(手动滑稽)

    附上代码...:

    package com.azimiao.trainning.controller;
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    
    public class graph {
    
        static int size; //定点个数
        static String[] vertexs; //图顶点名称
        static int[][] matrix ; //图关系矩阵矩阵
        static int[][] position; //储存位置信息
        static String[][] edges; //顶点的边关系
        static List<Map<String,Integer>> vertexmsg = new LinkedList<>(); //顶点详细信息
        static int[][] isroute;
    
        public static void readVertexs()throws Exception{
            //读取节点
            size = 35;
            vertexs = new String[size];
            BufferedReader bf1 = new BufferedReader(new FileReader("D:\\Project\\springBootTrain\\src\\main\\java\\com\\azimiao\\trainning\\controller\\vertexName.txt"));
            String str;
            int temp = 0;
            while ((str = bf1.readLine())!=null){
                vertexs[temp] = str;
                temp++;
            }
            bf1.close();
        }
    
        //建立矩阵图
        public static void buildGraph() {
            matrix = new int[size][size];
            for(int i = 0;i<edges.length;i++){
                for(int j = 1;j<edges[i].length;j++){
                    int position = 0;
                    while (!edges[i][j].equals(edges[position][0])) position++;
                    matrix[i][position] = 1;
                }
            }
        }
    
        //读取顶点边关系
        public static void readEdges()throws Exception{
            edges = new String[size][10];
            BufferedReader bf2 = new BufferedReader(new FileReader("D:\\Project\\springBootTrain\\src\\main\\java\\com\\azimiao\\trainning\\controller\\edges.txt"));
            for(int i =0 ;i<size;i++){
                edges[i] = bf2.readLine().split(",");
            }
            bf2.close();
        }
    
        //读取边的权重
        public static void readmsg()throws Exception{
            BufferedReader bf1 = new BufferedReader(new FileReader("D:\\Project\\springBootTrain\\src\\main\\java\\com\\azimiao\\trainning\\controller\\vertexmsg.txt"));
            String str;
            while ((str = bf1.readLine())!=null){
                String[] tempstr = str.split(",");
                Map<String,Integer> tempMap = new HashMap<>();
                for(int i =1;i<tempstr.length;i++){
                    if (i%2==0)  continue;
                    tempMap.put(tempstr[i],Integer.parseInt(tempstr[i+1]));
                }
                vertexmsg.add(tempMap);
            }
            bf1.close();
        }
    
        //读取位置信息
        public static void readPosition()throws Exception{
            position = new int[size][2];
            BufferedReader bf1 = new BufferedReader(new FileReader("D:\\Project\\springBootTrain\\src\\main\\java\\com\\azimiao\\trainning\\controller\\position.txt"));
            String str;
            int p = 0;
            while ((str = bf1.readLine())!=null){
                String[] tempstr = str.split(",");
                for(int i = 0 ;i<tempstr.length;i++){
                    position[p][i] = Integer.parseInt(tempstr[i]);
                }
                p++;
            }
        }
    
        public static void main(String[] args)throws Exception{
            //读取顶点
            readVertexs();
            //读取顶点的度
            readEdges();
            //获取图
            buildGraph();
            //读取位置
    //        readPosition();
    
            //遍历矩阵
            for(int i =0;i<position.length;i++){
                for(int j = 0;j<position[i].length;j++){
                    System.out.print(position[i][j]);
                    System.out.print("  ");
                }
                System.out.println();
            }
            readmsg();
            isroute = new int[size][size];
            dfs("GuangZhou","GuangZhou","HaErBin",new StringBuffer());
    
        }
    
        static StringBuffer strs = new StringBuffer();
        static int total;
        public static int dfs(String start,String curvertex,String terminal,StringBuffer sb){
            int position = 0;
            while (!start.equals(vertexs[position])) position++;
            if (start.equals(terminal)){
                System.out.println(total);
                System.out.println(strs.toString());
                strs = null;
                strs = new StringBuffer();
                total = 0;
                return 1;
            }
            for(int i = 0;i<matrix[position].length;i++){
                if(matrix[position][i]==1 && isroute[position][i]!=1  ){
    
                    total += vertexmsg.get(position).get(vertexs[i]);
                    isroute[position][i] = 1; //标记走过的边
                    isroute[i][position] = 1; //同上
                    strs.append("->"+vertexs[i]);
                    if(vertexs[i].equals(curvertex)){
                        strs = null;
                        strs = new StringBuffer();
                        total = 0;
                        return -1;
                    }
                    dfs(vertexs[i],curvertex,terminal,new StringBuffer().append(strs));
                }
            }
            strs = null;
            strs = new StringBuffer();
            total = 0;
            return -1;
        }
    }
    
    
    337136897
        1
    337136897  
    OP
       2018-11-27 15:11:47 +08:00
    -.-为啥会出现在第三页 咳咳
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1368 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 23:35 · PVG 07:35 · LAX 16:35 · JFK 19:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.