实现计算景点间通行的最短路径功能

需求分析

• 景区推荐
• 游客查询到达景区的最短路线

实现方案

考虑图论中的最短路径问题，将景区最短路线问题转换为图的最短路径问题，从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。

Dijkstra算法：

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

具体实现

构造图

// 景点信息类
public class AttractionInfo {
    String serialNum; //景点编号
    String attractionName; // 景点名称
    AttractionInfo(String num,String name){
        this.serialNum = num;
        this.attractionName = name;
    }
}

// 头结点
public class Node {
    AttractionInfo info;// 景点详细信息
    Enode firstAdj;// 相邻结点
    Node(AttractionInfo info){
        this.info = info;
    }

}

// 图结点
public class Enode {
    String serialNum; // 景点编号
    String weight;// 路径权重
    Enode(String serialNum,String weight){
        this.serialNum = serialNum;
        this.weight = weight;
    }
}

// 构造图的邻接表
public Pair<int[][],Node[]> buildGraph(int maxNum, List<GraphNode> list){
    numOfNode = 0;
    headArray = new Node[maxNum];
    edges = new int[maxNum][maxNum];
    for(int i = 0;i <maxNum;i++){
        for (int j = 0;j < maxNum;j++){
            edges[i][j]=Integer.MAX_VALUE;
        }
    }
    for(GraphNode graphNode:list){
        Integer num = graphNode.getSerialNum();
        String serialNum = String.valueOf(num);
        String attractionName = graphNode.getAttractionName();
        insertHead(serialNum,attractionName);
    }
    // 切割字符串后得到的数组
    /*
        第i行表示,与编号为i的景点相邻的景点, 也就是i的邻居
        [DijkstraUtil.Enode(serialNum=n2, weight=2), DijkstraUtil.Enode(serialNum=n3, weight=1), null, null]
        [DijkstraUtil.Enode(serialNum=n2, weight=13), DijkstraUtil.Enode(serialNum=n3, weight=1), null, null]
        [DijkstraUtil.Enode(serialNum=n0, weight=2), null, null, null]
        [DijkstraUtil.Enode(serialNum=n2, weight=2), DijkstraUtil.Enode(serialNum=n1, weight=1), DijkstraUtil.Enode(serialNum=n0, weight=10), null]
         */
    Enode[][] splitStringFromDB = new Enode[maxNum][maxNum];
    int index = 0;

    // 得到结点数组
    for(GraphNode graphNode:list){
        String adjacentNode = graphNode.getAdjacentNode();
        String[] split = adjacentNode.split(",");
        int index_1=0;
        for(String s:split){
            String[] split1 = s.split("-");
            Enode tempNode = new Enode(split1[0],split1[1]);
            splitStringFromDB[index][index_1++] = tempNode;
        }
        index++;
    }
    // 遍历splitStringFromDB数组 构造edges数组
    for(int i = 0;i < maxNum;i++){
        for (int j =0;j < maxNum;j++){
            if(splitStringFromDB[i][j] == null){
                break;
            }
            insertEdge(i,Integer.valueOf(splitStringFromDB[i][j].getSerialNum()),
                       Integer.valueOf(splitStringFromDB[i][j].getWeight()));
        }
    }
    return Pair.of(edges,headArray);

Dijkstra算法具体实现

/**
     * Dijkstra算法
     * @param edges
     * @param headArray
     * @param start
     */
public Pair<int[],List<String>[]> dijkstra(int[][] edges, Node[] headArray, int start){
    int numberOfNode = edges.length;
    List<String >[] path = new List[numberOfNode];
    for (int i = 0; i < numberOfNode; i++) {
        path[i] = new ArrayList<>();
    }
    path[start].add(String.valueOf(start));
    boolean[] visited = new boolean[numberOfNode];
    int[] dist = new int[numberOfNode];
    for (int i = 0;i < numberOfNode;i++){
        dist[i] = Integer.MAX_VALUE;
    }
    dist[start] = 0;
    for(int count = 0;count < numberOfNode - 1;count++){
        int u = minDist(dist,visited,numberOfNode);
        visited[u] = true;
        // 算法主体
        for(int i = 0;i < numberOfNode;i++){
            if((edges[u][i] != Integer.MAX_VALUE) && !visited[i] && (dist[i] > dist[u] + edges[u][i])){
                dist[i] = dist[u] + edges[u][i];
                String oldPath = path[u].toString();
                List<Integer> tempList = new ArrayList<>();
                path[i] = new ArrayList<>();
                path[i].add(String.valueOf(i));
                for(String s:path[u] ){
                    path[i].add(s);
                }
            }
        }
    }

    return Pair.of(dist,path);
}
private int minDist(int[] dist,boolean[] visited,int numOfNode){
    int min = Integer.MAX_VALUE;
    int minIndex = -1;
    for(int v = 0;v < numOfNode;v++){
        if(!visited[v] && dist[v] <= min){
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}