基于最短路径的深度遍历算法以及有站序控制的路径规划算法

迈不过友情╰ 2021-11-16 17:18 167阅读 0赞

由于产品的需求，现要对一批又起始站的站点规划一条最短路径出来。需求大概就是下图的意思：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70][]

再查询了最短路径算法后，[Dijkstra算法和Floyd算法][Dijkstra_Floyd] 后，感觉不符合我的需求，然后就自己琢磨写一个算法出来。

package com.data1.map;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * @author :zoboy
     * @Description:
     * @ Date: Created in 2019-07-26 14:54
     */
    public class ZJStationPath {
        private List<Node> tmpArr = new ArrayList<>();
        private List<Node[]> resultList = new ArrayList<>();
        private Map<String, Double> distanceMap = new HashMap<>();
        private List<Node> nodeList;
        private Node firstNode;
    
        static class Node {
            private String id;
            private List<String> flag;
    
            public List<String> getFlag() {
                return flag;
            }
    
            public void setFlag(List<String> flag) {
                this.flag = flag;
            }
    
            public String getId() {
                return id;
            }
    
            public void setId(String id) {
                this.id = id;
            }
        }
    
        ZJStationPath(List<Node> nodeList, Map<String, Double> distanceMap, Node firstNode) {
            this.nodeList = nodeList;
            this.distanceMap = distanceMap;
            this.firstNode = firstNode;
        }
    
        public Node[] getPath() {
            arrangement(nodeList.size(), nodeList);
            double min = 0.00;
            Node[] nodes = new Node[nodeList.size()];
            for (int i = 0; i < resultList.size(); i++) {
                double distance = print(i);
                if (min <= distance) {
                    min = distance;
                    nodes = resultList.get(i);
                }
            }
            return nodes;
        }
    
        public double print(int i) {
            double distance = 0.00;
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < resultList.get(i).length; j++) {
                if (j >= 1) {
                    String key = resultList.get(i)[j - 1].getId() + "-" + resultList.get(i)[j].getId();
                    distance += distanceMap.get(key);
                }
                stringBuilder.append(resultList.get(i)[j].getId() + ",");
            }
            stringBuilder.append("distance:" + distance);
            System.out.println(stringBuilder.toString());
            return distance;
        }
    
        public void covertData(List<Node> nodeList) {
            Node[] nodes = new Node[nodeList.size()];
            for (int i=0;i<nodeList.size();i++){
                nodes[i]=nodeList.get(i);
            }
            resultList.add(nodes);
        }
    
        public void arrangement(int k, List<Node> nodeList) {
            if (k == 1) {
                for (int i = 0; i < nodeList.size(); i++) {
                    tmpArr.add(nodeList.get(i));
                    System.out.println();
                    for (Node node:tmpArr){
                        System.out.print(node.getId()+"->");
                    }
                    covertData(tmpArr);
                    tmpArr.remove(nodeList.get(i));
                }
            } else if (k > 1) {
                for (int i = 0; i < nodeList.size(); i++) { //按顺序挑选一个元素
                    Node node = nodeList.get(i);
                    if(judeFirstStation() && !judeStationSeq(node,nodeList) ){
                        tmpArr.add(node); //添加选到的元素
                        List<Node> remainList = removeArrayElements(nodeList, tmpArr);
                        arrangement(k - 1, remainList); //没有取过的元素，继续挑选
                        tmpArr.remove(nodeList.get(i));
                    }
                }
            } else {
                return;
            }
        }
    
        public Boolean judeFirstStation(){
            Boolean isFirstNode=true;
            if (firstNode != null && tmpArr!=null && tmpArr.size()>0) {
                if (!firstNode.getId().equals(tmpArr.get(0).getId())) {
                    isFirstNode= false;
                }
            }
            return isFirstNode;
        }
    
        public Boolean judeStationSeq(Node currentNode, List<Node> nodeList) {
            List<String> flags = currentNode.getFlag();
            List<Node> nodeList1 = new ArrayList<>();
            nodeList1.add(currentNode);
            for (String flag : flags) {
                //从剩下的node中找是否当前node在剩下的所有node之前
                List<Node> remainList = removeArrayElements(nodeList, nodeList1);
                String outKey = flag.split("-")[0];
                int outSort = Integer.parseInt(flag.split("-")[1]);
                for (int i=0;i<remainList.size();i++) {
                    Node nextNode=remainList.get(i);
                    List<String> nextFlags = nextNode.getFlag();
                    for (String nextflag : nextFlags) {
                        String innerKey = nextflag.split("-")[0];
                        if (outKey.equals(innerKey)) {
                            int innerSort = Integer.parseInt(nextflag.split("-")[1]);
                            if (outSort > innerSort) {
                                return true;
                            }
                            nodeList1.add(nextNode);
                        }
                    }
                }
            }
            return false;
        }
    
    
        public List<Node> removeArrayElements(List<Node> nodeList, List<Node> tmpArr) {
            List<Node> remainList = new ArrayList<>(nodeList.size());
            for (int i = 0; i < nodeList.size(); i++) {
                boolean find = false;
                for (int j = 0; j < tmpArr.size(); j++) {
                    if (nodeList.get(i).getId().equals(tmpArr.get(j).getId())) {
                        find = true;
                        break;
                    }
                }
                if (!find) { //没有找到的元素保留下来
                    remainList.add(nodeList.get(i));
                }
            }
            return remainList;
        }
    }

这就算法的实现过程，下面附一个测试类：

package com.data1.map;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * @author :zoboy
     * @Description:
     * @ Date: Created in 2019-07-26 14:56
     */
    public class Test1 {
    
        public static void main(String[] args) {
            long startTime=System.currentTimeMillis();
            List<ZJStationPath.Node> nodeList = init();
            Map<String,Double> distanceList = new HashMap<>();
            for(ZJStationPath.Node node1 :nodeList ){
                for(ZJStationPath.Node node2 :nodeList ){
                    if(!node1.getId().equals(node2.getId())){
                        distanceList.put(node1.getId()+"-"+node2.getId(),Math.random()*10+1000);
                    }
                }
            }
            ZJStationPath.Node firstNode = nodeList.get(0);
            ZJStationPath zjStationPath = new ZJStationPath(nodeList,distanceList,firstNode);
            ZJStationPath.Node [] nodes= zjStationPath.getPath();
            System.out.println(nodes.length+"个点的最短路径结果：");
            for (ZJStationPath.Node node:nodes){
                System.out.print(node.getId()+"->");
            }
            long endTime=System.currentTimeMillis();
            System.out.println("程序运行时间： "+(endTime - startTime)/1000+"s");
        }
    
        public static List<ZJStationPath.Node> init(){
            ZJStationPath.Node A = new ZJStationPath.Node();
            A.setId("A");
            List<String> flag = new ArrayList<>();
            flag.add("AB-1");
            flag.add("AC-1");
            flag.add("AD-1");
            A.setFlag(flag);
            ZJStationPath.Node B = new ZJStationPath.Node();
            B.setId("B");
            flag = new ArrayList<>();
            flag.add("AB-2");
            B.setFlag(flag);
            ZJStationPath.Node C = new ZJStationPath.Node();
            C.setId("C");
            flag = new ArrayList<>();
            flag.add("AC-2");
            C.setFlag(flag);
            ZJStationPath.Node D = new ZJStationPath.Node();
            D.setId("D");
            flag = new ArrayList<>();
            flag.add("AD-2");
            D.setFlag(flag);
            ZJStationPath.Node E = new ZJStationPath.Node();
            E.setId("E");
            flag = new ArrayList<>();
            flag.add("EF-1");
            E.setFlag(flag);
            ZJStationPath.Node F = new ZJStationPath.Node();
            F.setId("F");
            flag = new ArrayList<>();
            flag.add("EF-2");
            F.setFlag(flag);
            List<ZJStationPath.Node> nodeList = new ArrayList<>();
            nodeList.add(A);
            nodeList.add(B);
            nodeList.add(C);
            nodeList.add(E);
            nodeList.add(D);
            nodeList.add(F);
            return nodeList;
        }
    
    
    }

下面是运行结果：

![20190729095359887.png][]

具体的实现过程或者想法请qq（418546333）或者微信（hi-zoboy）我

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70]: /images/20211116/901b6f20edc64322af6338a4938b4d43.png
[Dijkstra_Floyd]: https://www.cnblogs.com/wsw-seu/p/8185285.html
[20190729095359887.png]: /images/20211116/cbef132c43f04e88a869425df7c17c99.png