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

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

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

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

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

附上代码...:

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;
    }
}