博客

Java 实现无向连通图的经过所有点且最短路径算法

最近有一个需求 ，就是给北环做的环卫项目，垃圾清收车的调度，就是在某个区域已满的垃圾桶进行清收，

要不重复的经过所有的垃圾桶，要求路程最短，因为我们的主要负责奥体公园，所以今天写了下面的算法，这个的缺点是，计算超过三十个

清收点时，需要首先找到一个近似最优的结果来过滤许多的计算 经我测试 可以提前计算近似解 来提高效率 哈哈

就是一张纸上有N个点 ,用笔连接所有的点,找出路径最小的画法

代码都有注释

代码

/*
求出最短路径
 */
public class MiniDis {

    static  double INF = 1e7;
    static  int N = 100;
    static  double[][] matrix ;  //地图矩阵
    static  Node min;
    static  double bestl = INF;// 记录当前最短的路径长度
    static  List<Integer> nodes = new ArrayList<Integer>();
    static  PriorityQueue<Node> priorityQueue = new PriorityQueue<>(N/2);


    // 优先队列的分支界限法搜索
    static double Traveling(){
        nodes.add(2);
        nodes.add(3);
        nodes.add(4);
        nodes.add(5);

        matrix = new double[][]{
                {0,0,0,0,0,0},
                {0,INF,15,30,5,9},
                {0,15,INF,6,12,3},
                {0,30,6,INF,3,8},
                {0,5,12,3,INF,6},
                {0,9,3,9,8,INF},
        };


        //生成根节点
        Node root = new Node(0, 1);
        root.notThrough.addAll(nodes);
        root.throughed.add(1);
        // 生成所有要走的点节点
        priorityQueue.add(root);

        while (!priorityQueue.isEmpty()){
            // 取出头部元素作为扩展节点
            Node poll = priorityQueue.poll();

            // 如果当前的未到达路径只有一个  不需要往下搜索
            if (poll.notThrough.size()==1){
                // 如果当前节点和未达节点可联通
                for (Integer not: poll.notThrough) {
                    if (matrix[poll.id][not]!=INF && matrix[poll.id][not]+poll.c1 < bestl ){
                        bestl = matrix[poll.id][not]+poll.c1;
                        poll.throughed.add(not);
                        min=poll;
                    }
                }
            }

            // 如果没有到达子节点 遍历该节点没有经过的节点
            for (Integer noThrough : poll.notThrough){
                // 如果当前节点和未达节点可联通
                if (matrix[poll.id][noThrough]==INF){
                    continue;
                }
                //并且 到达的路径小于当前最优解
                if (matrix[poll.id][noThrough]+poll.c1 < bestl){

                    Node newNode = new Node(matrix[poll.id][noThrough] + poll.c1, noThrough);

                    HashSet<Integer> noth = new HashSet<>(poll.notThrough);

                    noth.remove(noThrough);
                    // 新结点去除上一个节点没通过的自己的Id
                    newNode.notThrough.addAll(noth);
                    // 新结点保存之前node经过的点
                    newNode.throughed.addAll(poll.throughed);
                    // 新结点记录经过的点
                    newNode.throughed.add(noThrough);

                    priorityQueue.add(newNode);
                }
            }
        }
        System.out.println(bestl);
        System.out.println(min.throughed);
        return bestl;
    }
    //内部类 node  //根据c1大小实现优先级
    static class Node implements Comparable<Node> {
        public double c1; // 当前已走过的路径长度
        public int id; //点序号
        public LinkedHashSet<Integer> throughed; // 当前已走过的点序号
        public HashSet<Integer> notThrough; //当前未走过的点序号

        public Node(double c1, int id) {
            this.c1 = c1;
            this.id = id;
            this.notThrough= new HashSet<>();
            this.throughed=new LinkedHashSet<>();
        }

        @Override
        public int compareTo(Node o) {
            return (int) (this.c1-o.c1);
        }
    }
    public static void main(String[] args) {
        Traveling();
    }


}