多线程并行 Dijkstra与A*算法结合实践

多线程并行 Dijkstra与A*算法融合

1、Dijkstra总能找到最优解 但是时间消耗大 ，本文实现了多线程并行的搜索算法，使得路径搜素时间缩短约1/3

2、H作为传入参数可以使得本算法可以切换为A*也可以变为Dijkstra

3、本算法使得空间复杂度增加

4、程序构造了一个路网测试程序、后续准备进行路网随机生成测试

算法主程序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
//并行计算主程序
public class CalculateThread extends Thread  {

    private Graph g;
    private Vertex from;
    private Vertex to;

    private Vertex result;
    private Double coefficientH;
    private Double coefficientG;
    CountDownLatch latch;
    private List<Vertex> openList = Collections.synchronizedList(new ArrayList<Vertex>());
    private List<Vertex> closeList = Collections.synchronizedList(new ArrayList<Vertex>());
    double sum = 0.0;

    public Vertex getResult() {
        return result;
    }

    public void setResult(Vertex result) {
        this.result = result;
    }

    public CalculateThread(Graph g, Vertex from, Vertex to, Double coefficientH, Double coefficientG,CountDownLatch latch){
        this.from = from;
        this.to = to;
        this.g = g;
        this.coefficientH = coefficientH;
        this.coefficientG = coefficientG;

        this.latch = latch;

    }

    @Override
    public void run() {
        long startTime = System.currentTimeMillis();    //获取开始时间

        int flag =0;
        //while(flag<100) {

            Vertex parent = AstarCalculate(g, from, to, coefficientH, coefficientG);
            List<Vertex> arrayList = Collections.synchronizedList(new ArrayList<Vertex>());


            arrayList = parent != from ? getPaths(parent, from) : null;
            //System.out.println(arrayList.toString());
            //System.out.println("arrayList.size()"+arrayList.size());
            // System.out.println("计算结束");
            if (arrayList.size() > 0) {
                for (int i = 0; i < arrayList.size()-1; i++) {
                    for (Path path : g.PathHashSet) {
                        if (path.getFrom().nodeId.equals(arrayList.get(i).nodeId) && path.getTo().nodeId.equals(arrayList.get(i + 1).nodeId)
                                || path.getFrom().nodeId.equals(arrayList.get(i + 1).nodeId) && path.getTo().nodeId.equals(arrayList.get(i).nodeId)) {
                            sum += path.getWeight();

                        }
                    }
                }
            }
        Collections.reverse(arrayList);
            System.out.println("sum" + sum + "  arrayList"+arrayList.toString());

           // System.out.println(Thread.currentThread().getName() + "coefficientH: " + coefficientH);
           // System.out.println(arrayList.toString());
            flag++;
        //}
        long endTime = System.currentTimeMillis();    //获取结束时间

        System.out.println("计算结束运行时间：" + (endTime - startTime) + "ms");    //输出程序运行时间

        System.out.println("latch.countDown()");
        latch.countDown();
    }


    public Vertex AstarCalculate(Graph g, Vertex from, Vertex to, Double coefficientH, Double coefficientG) {
        List<Vertex> neighbour = from.getNeighbours();
        this.coefficientH = coefficientH;
        this.coefficientG = coefficientG;
        from.setErgodic(true);
        openList.add(from);

        openList.remove("2");
        closeList.add(g.vertexHashMap.get("2"));
        int flag =0;
        System.out.println("from: "+from);
        while (openList.size() > 0) {
            Vertex currentNode = findMinFVertexInOpneList();
            openList.remove(currentNode);
            closeList.add(currentNode);
            List<Vertex> neighborNodes = findNeighborNodes(currentNode);
            for(int k=0;k<closeList.size();k++){
                neighborNodes.remove(closeList.get(k));
            }
            for (Vertex node : neighborNodes) {
                flag++;
                if (exists(openList, node)) {
                    foundPoint(currentNode, node,g);
                } else {
                    notFoundPoint(currentNode, to, node,g);
                }
            }
            if (find(openList, to) != null) {
                System.out.println("遍历节点: "+flag);
                return find(openList, to);
            }
        }
        System.out.println("遍历节点: "+flag);
        return find(openList, to);

    }
    private synchronized  void foundPoint(Vertex tempStart, Vertex node,Graph g) {
        Double G = calcG2(tempStart, node,g);
        if (G < node.G) {
            node.parent = tempStart;
            node.G = G;
            node.calcF();
        }
    }
    private void notFoundPoint(Vertex tempStart, Vertex end, Vertex node,Graph g) {
        node.parent = tempStart;
        node.G = calcG(tempStart, node,g);
        //System.out.println("node.G: "+node.G);
        node.H = calcH(end, node);
        node.calcF();
        // System.out.println("node.getF(): "+node.getF());
        openList.add(node);
    }
    public Vertex findMinFVertexInOpneList() {
        Vertex bestNode = null;
        double bestF = Double.MAX_VALUE;
        for(Vertex node: openList){
            if(node.getF() < bestF){
                bestF = node.getF();
                bestNode = node;
            }
        }
        return bestNode;

    }

    private static ArrayList<Vertex> getPaths(Vertex endNode,Vertex startNode) {
        ArrayList<Vertex> arrayList = new ArrayList<Vertex>();
        Vertex pre = endNode;
        int flag =0;
        while (pre.nodeId != startNode.nodeId && flag<200) {
            arrayList.add(new Vertex(pre.nodeId, pre.x, pre.y, pre.isErgodic, pre.totalDistance));
            pre = pre.parent;
            flag++;
        }
        arrayList.add(new Vertex(startNode.nodeId, startNode.x, startNode.y, startNode.isErgodic, startNode.totalDistance));
        return arrayList;
    }

    public List<Vertex> findNeighborNodes(Vertex currentNode) {
        return currentNode.getNeighbours();
    }

    public static boolean exists(List<Vertex> maps, Vertex node) {
        for (Vertex n : maps) {
            if ((n.x == node.x ) && (n.y == node.y)) {
                return true;
            }
        }
        return false;
    }

    public static Vertex find(List<Vertex> maps, Vertex point) {
        for (Vertex n : maps)
            if ((n.x == point.x ) && (n.y == point.y)) {
                return n;
            }
        return null;
    }




    private Double calcG(Vertex start, Vertex node,Graph g) {

       // System.out.println("calcG: ");
       // System.out.println("start: "+ start);
       // System.out.println("node: "+ node);
       // System.out.println("PathHashSet: "+ g.PathHashSet);
        Double G = 0.0;
        for (Path path : g.PathHashSet) {
            if(path.getFrom().nodeId.equals(node.nodeId) && path.getTo().nodeId.equals(start.nodeId)){
                G = coefficientG*path.getWeight();
            }else if(path.getFrom().nodeId.equals(start.nodeId) && path.getTo().nodeId.equals(node.nodeId)){
                G = coefficientG*path.getWeight();
            }
        }
        //System.out.println("G: "+G);
        Double parentG = node.parent != null ? node.parent.G : 0;

        return G + parentG;
    }

    private Double calcG2(Vertex start, Vertex node,Graph g) {
        Double G = 0.0;
        for (Path path : g.PathHashSet) {
            if(path.getFrom().nodeId.equals(node.nodeId) && path.getTo().nodeId.equals(start.nodeId)){
                G = coefficientG*path.getWeight();
            }else if(path.getFrom().nodeId.equals(start.nodeId) && path.getTo().nodeId.equals(node.nodeId)){
                G = coefficientG*path.getWeight();
            }
        }
        //Double parentG = start.parent != null ? start.parent.G : 0;
        Double parentG = start.getG();
        return G + parentG;
    }

    private Double calcH(Vertex end, Vertex node) {
        Double step = coefficientH*((node.x - end.x)*(node.x - end.x) + (node.y - end.y)*(node.y - end.y));
        return Math.sqrt(step);
        // return 0.0;
    }
}

路径实体类

package com.graph;

import com.sun.javafx.scene.traversal.WeightedClosestCorner;

public class Path {

    Double Weight;
    private Vertex from;
    private Vertex to;


    public Path(Double weight, Vertex from, Vertex to) {
        Weight = weight;
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return "Path{" +
                "Weight=" + Weight +
                ", from=" + from +
                ", to=" + to +
                '}';
    }

    public Double getWeight() {
        return Weight;
    }

    public void setWeight(Double weight) {
        Weight = weight;
    }

    public Vertex getFrom() {
        return from;
    }

    public void setFrom(Vertex from) {
        this.from = from;
    }

    public Vertex getTo() {
        return to;
    }

    public void setTo(Vertex to) {
        this.to = to;
    }
}

顶点实体类

package com.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Vertex {

    String nodeId;
    Double x;
    Double y;
    Boolean isErgodic;
    float totalDistance;
    private LinkedList<Vertex> neighbours;

    public Double F;
    public Double G;
    public Double H;
    public Vertex parent;



    public Vertex(String nodeId, Double x, Double y, Boolean isErgodic, float totalDistance, LinkedList<Vertex> neighbours) {
        this.nodeId = nodeId;
        this.x = x;
        this.y = y;
        this.isErgodic = isErgodic;
        this.totalDistance = totalDistance;
        this.neighbours = neighbours;
        this.G = 0.0;
        this.F = 0.0;
        this.H = 0.0;
    }
    public Vertex(Vertex v) {
        this.nodeId = v.nodeId;
        this.x = v.x;
        this.y = v.y;
        this.isErgodic = v.isErgodic;
        this.totalDistance = v.totalDistance;
        this.neighbours = v.neighbours;
        this.G =  v.G;
        this.F =  v.F;
        this.H =  v.H;
    }

    public Vertex(String nodeId, Double x, Double y, Boolean isErgodic, float totalDistance) {
        this.nodeId = nodeId;
        this.x = x;
        this.y = y;
        this.isErgodic = isErgodic;
        this.totalDistance = totalDistance;
        this.neighbours = new LinkedList<Vertex>();

    }

    public Vertex() {

    }

    @Override
    public String toString() {
        return "Vertex{" +
                "nodeId='" + nodeId + '\'' +

                '}';
    }

    public void calcF() {
        //this.F = this.G + this.H;
        this.F = this.G;
    }

    public Double getF() {
        return F;
    }

    public void setF(Double f) {
        F = f;
    }

    public Double getG() {
        return G;
    }

    public void setG(Double g) {
        G = g;
    }

    public Double getH() {
        return H;
    }

    public void setH(Double h) {
        H = h;
    }

    public Vertex getParent() {
        return parent;
    }

    public void setParent(Vertex parent) {
        this.parent = parent;
    }


    public float getTotalDistance() {
        return totalDistance;
    }

    public void setTotalDistance(float totalDistance) {
        this.totalDistance = totalDistance;
    }

    public LinkedList<Vertex> getNeighbours() {
        return neighbours;
    }

    public void setNeighbours(LinkedList<Vertex> neighbours) {
        this.neighbours = neighbours;
    }

    public String getNodeId() {
        return nodeId;
    }

    public Double getX() {
        return x;
    }

    public Double getY() {
        return y;
    }

    public Boolean getErgodic() {
        return isErgodic;
    }

    public void setNodeId(String nodeId) {
        this.nodeId = nodeId;
    }

    public void setX(Double x) {
        this.x = x;
    }

    public void setY(Double y) {
        this.y = y;
    }

    public void setErgodic(Boolean ergodic) {
        isErgodic = ergodic;
    }


}

图的构造初始化：

package com.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Graph {

    public ConcurrentHashMap<String, Vertex> vertexHashMap;
    public ConcurrentHashSet<Path> PathHashSet;

    @Override
    public String toString() {
        return "Graph{" +
                "vertexHashMap=" + vertexHashMap +
                ", PathHashSet=" + PathHashSet +
                '}';
    }

    public Vertex findVertex(String id){
       return (Vertex)vertexHashMap.get(id);
    }

    public Graph (ConcurrentHashMap<String,Vertex> vertexHashMap, ConcurrentHashSet<Path> PathHashSet) {
        this.vertexHashMap = vertexHashMap;
        this.PathHashSet = PathHashSet;

        for (String key : vertexHashMap.keySet()) {
            for (Path path : PathHashSet) {
                if(path.getTo().nodeId.equals(vertexHashMap.get(key).nodeId)){
                    Vertex v2 = new Vertex();
                    v2 = vertexHashMap.get(path.getFrom().nodeId);
                   // LinkedList<Vertex>  list = v.getNeighbours();
                  //  list.add(v2);
                    vertexHashMap.get(key).getNeighbours().add(v2);
                }else if(path.getFrom().nodeId.equals(vertexHashMap.get(key).nodeId)){
                    Vertex v2 = new Vertex();
                    v2 = vertexHashMap.get(path.getTo().nodeId);
                    vertexHashMap.get(key).getNeighbours().add(v2);
                }
            }

        }
    }
}

计算方法构造

package com.graph;

import com.Dijkstra.ParallelAstarRunnable;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import static java.lang.Thread.sleep;

public  class  Calculate  {

    private List<Vertex> openList = Collections.synchronizedList(new ArrayList<Vertex>());
    private List<Vertex> closeList = Collections.synchronizedList(new ArrayList<Vertex>());



    public List<Vertex> getOpenList() {
        return openList;
    }

    public void setOpenList(List<Vertex> openList) {
        this.openList = openList;
    }

    public List<Vertex> getCloseList() {
        return closeList;
    }

    public void setCloseList(List<Vertex> closeList) {
        this.closeList = closeList;
    }

    public double getSum() {
        return sum;
    }

    public void setSum(double sum) {
        this.sum = sum;
    }

    public Double getCoefficientH() {
        return coefficientH;
    }

    public void setCoefficientH(Double coefficientH) {
        this.coefficientH = coefficientH;
    }

    public Double getCoefficientG() {
        return coefficientG;
    }

    public void setCoefficientG(Double coefficientG) {
        this.coefficientG = coefficientG;
    }

    double sum = 0.0;

    Double coefficientH =0.0;
    Double coefficientG = 0.0;



    public void AstarPath(ConcurrentHashMap<String, Vertex> vertexHashMap, ConcurrentHashSet<Path> PathHashSet, Vertex v2, Vertex v5,Double coefficientH,Double coefficientG){
             System.out.println("开始计算");
        long startTime = System.currentTimeMillis();    //获取开始时间

            Graph g = new Graph(vertexHashMap,PathHashSet);

           // Vertex parent =  AstarCalculate(g,v2,v5,coefficientH,coefficientG);
            //System.out.println(parent);

           // List<Vertex> arrayList = Collections.synchronizedList(new ArrayList<Vertex>());
           // arrayList = parent != v2 ? getPaths(parent,v2) : null;
            //System.out.println("arrayList.size()"+arrayList.size());
             //System.out.println("计算结束");

            // if(arrayList.size()>0){
        /*for (int i = 0; i < arrayList.size()-1; i++) {
            for (Path path : g.PathHashSet) {
                if(path.getFrom().nodeId.equals(arrayList.get(i).nodeId) && path.getTo().nodeId.equals(arrayList.get(i+1).nodeId)
                        || path.getFrom().nodeId.equals(arrayList.get(i+1).nodeId) && path.getTo().nodeId.equals(arrayList.get(i).nodeId)){
                    sum += path.getWeight();

                }
            }
        }
             }
        System.out.println("sum"+ sum);

        Collections.reverse(arrayList);
        System.out.println(Thread.currentThread().getName()+"coefficientH: "+coefficientH);
        System.out.println(arrayList.toString());*/
        }


    public Vertex AstarCalculate(ArrayList<Graph> graphs, Vertex from, Vertex to,Double coefficientH,Double coefficientG) {
        ExecutorService pool = Executors.newFixedThreadPool(16);
        List<Vertex> neighbour = from.getNeighbours();
        this.coefficientH = coefficientH;
        this.coefficientG = coefficientG;
        from.setErgodic(true);
        openList.add(from);
        Vector<Thread> threadVector =  new Vector<Thread>();
        Vertex currentNode = findMinFVertexInOpneList();
        List<Vertex> neighborNodes2 = new ArrayList<Vertex>();
        neighborNodes2 = findNeighborNodes(currentNode);
        final CountDownLatch latch = new CountDownLatch(neighborNodes2.size());
        // for (Vertex node : neighborNodes2) {
        // Graph g2 = new Graph(g.vertexHashMap,g.PathHashSet);
       // Vertex from2 = g.vertexHashMap.get("3");
        //pool.submit(new CalculateThread(g, g.vertexHashMap.get("5"), to, coefficientH,coefficientG,latch));
        CalculateThread v1 = new CalculateThread(graphs.get(0), graphs.get(0).vertexHashMap.get("3"), to, coefficientH,coefficientG,latch);
        CalculateThread v2 = new CalculateThread(graphs.get(1), graphs.get(1).vertexHashMap.get("4"), to, coefficientH,coefficientG,latch);
        CalculateThread v3 = new CalculateThread(graphs.get(2), graphs.get(2).vertexHashMap.get("5"), to, coefficientH,coefficientG,latch);
        CalculateThread v4 = new CalculateThread(graphs.get(3), graphs.get(3).vertexHashMap.get("11"), to, coefficientH,coefficientG,latch);
        CalculateThread v5 = new CalculateThread(graphs.get(4), graphs.get(4).vertexHashMap.get("1"), to, coefficientH,coefficientG,latch);
        pool.submit(v1);
        pool.submit(v2);
        pool.submit(v3);
        pool.submit(v4);
        pool.submit(v5);
        //}
        try {
            latch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("main Thread go on");
        pool.shutdown();
        return find(openList, to);
    }

}

图形节点与path初始化构造：

package com.graph;

import javax.management.StringValueExp;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

public class ParallelAstarRunnable3 {


    Double coefficientH =0.0;
    Double coefficientG =0.0;

    ParallelAstarRunnable3(Double coefficientH,Double coefficientG){
        this.coefficientH = coefficientH;
        this.coefficientG = coefficientG;
    }


    public void cal() {



        Calculate a = new Calculate();
        // LinkedList<Vertex> list = new LinkedList<Vertex>();
        List<Vertex> list = new LinkedList<Vertex>();


        Vertex v1 = new Vertex("1", 0.0, 3.0, false,0,new LinkedList<Vertex>());
        Vertex v2 = new Vertex("2", 2.0, 0.0, false,0,new LinkedList<Vertex>());
        Vertex v3 = new Vertex("3", 1.5, 3.0, false,0,new LinkedList<Vertex>());
        Vertex v4 = new Vertex("4", 4.0, 2.0, false,0,new LinkedList<Vertex>());
        Vertex v5 = new Vertex("5", 8.0, 0.0, false,0,new LinkedList<Vertex>());
        Vertex v6 = new Vertex("6", 6.0, 6.0, false,0,new LinkedList<Vertex>());
        Vertex v7 = new Vertex("7", 4.0, 7.0, false,0,new LinkedList<Vertex>());
        Vertex v8 = new Vertex("8", 3.0, 9.0, false,0,new LinkedList<Vertex>());
        Vertex v9 = new Vertex("9", 4.0, 11.0, false,0,new LinkedList<Vertex>());
        Vertex v10 = new Vertex("10", 8.0, 8.0, false,0,new LinkedList<Vertex>());
        Vertex v11 = new Vertex("11", 8.0, 3.0, false,0,new LinkedList<Vertex>());
        Vertex v12 = new Vertex("12", 10.0, 5.0, false,0,new LinkedList<Vertex>());

        list.add(v1);
        list.add(v2);
        list.add(v3);
        list.add(v4);
        list.add(v5);
        list.add(v6);
        list.add(v7);
        list.add(v8);
        list.add(v9);
        list.add(v10);
        list.add(v11);
        list.add(v12);


        ConcurrentHashMap conMap = new ConcurrentHashMap<String, Vertex>();
        ConcurrentHashMap conMap2 = new ConcurrentHashMap<String, Vertex>();
        ConcurrentHashMap conMap3 = new ConcurrentHashMap<String, Vertex>();
        ConcurrentHashMap conMap4 = new ConcurrentHashMap<String, Vertex>();
        ConcurrentHashMap conMap5 = new ConcurrentHashMap<String, Vertex>();
        //Vertex(String nodeId, Double x, Double y, Boolean isErgodic, float totalDistance, LinkedList<Vertex> neighbours)
        for(int i = 0; i< 12 ;i++){
            conMap.put(String.valueOf(i+1),new Vertex(list.get(i).getNodeId(),list.get(i).getX(),list.get(i).getY(),list.get(i).isErgodic,list.get(i).getTotalDistance(),new LinkedList<Vertex>()));
            conMap2.put(String.valueOf(i+1),new Vertex(list.get(i).getNodeId(),list.get(i).getX(),list.get(i).getY(),list.get(i).isErgodic,list.get(i).getTotalDistance(),new LinkedList<Vertex>()));
            conMap3.put(String.valueOf(i+1),new Vertex(list.get(i).getNodeId(),list.get(i).getX(),list.get(i).getY(),list.get(i).isErgodic,list.get(i).getTotalDistance(),new LinkedList<Vertex>()));
            conMap4.put(String.valueOf(i+1),new Vertex(list.get(i).getNodeId(),list.get(i).getX(),list.get(i).getY(),list.get(i).isErgodic,list.get(i).getTotalDistance(),new LinkedList<Vertex>()));
            conMap5.put(String.valueOf(i+1),new Vertex(list.get(i).getNodeId(),list.get(i).getX(),list.get(i).getY(),list.get(i).isErgodic,list.get(i).getTotalDistance(),new LinkedList<Vertex>()));

        }
        List<ConcurrentHashMap> ConcurrentHashMaplist = new LinkedList<ConcurrentHashMap>();
        ConcurrentHashMaplist.add(conMap);
        ConcurrentHashMaplist.add(conMap2);
        ConcurrentHashMaplist.add(conMap3);
        ConcurrentHashMaplist.add(conMap4);
        ConcurrentHashMaplist.add(conMap5);

        ConcurrentHashSet<Path> pathSet = new ConcurrentHashSet<Path>();
        ConcurrentHashSet<Path> pathSet2 = new ConcurrentHashSet<Path>();
        ConcurrentHashSet<Path> pathSet3 = new ConcurrentHashSet<Path>();
        ConcurrentHashSet<Path> pathSet4 = new ConcurrentHashSet<Path>();
        ConcurrentHashSet<Path> pathSet5 = new ConcurrentHashSet<Path>();
        List<Path> listpath = new LinkedList<Path>();
        List<ConcurrentHashSet<Path>> listPathset =new LinkedList<ConcurrentHashSet<Path>>();
        for(int i =0;i<ConcurrentHashMaplist.size();i++){
            listpath.add(new Path(1.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("1")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("2"))));
            listpath.add(new Path(2.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("1")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("8"))));
            listpath.add(new Path(1.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("8")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("9"))));
            listpath.add(new Path(1.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("7")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("8"))));
            listpath.add(new Path(4.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("7")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("4"))));

            listpath.add(new Path(2.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("11")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("5"))));
            listpath.add(new Path(2.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("3")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("4"))));
            listpath.add(new Path(2.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("3")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("2"))));
            listpath.add(new Path(5.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("2")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("4"))));
            listpath.add(new Path(3.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("2")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("5"))));

            listpath.add(new Path(8.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("2")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("11"))));
            listpath.add(new Path(1.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("4")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("11"))));
            listpath.add(new Path(3.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("10")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("11"))));
            listpath.add(new Path(1.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("11")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("12"))));
            listpath.add(new Path(3.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("7")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("6"))));

            listpath.add(new Path(8.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("4")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("6"))));
            listpath.add(new Path(2.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("6")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("10"))));
            listpath.add(new Path(4.0, new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("8")), new Vertex((Vertex)ConcurrentHashMaplist.get(i).get("10"))));

        }


        for(int i =0;i<18;i++){
            pathSet.add(listpath.get(i));
        }
        for(int i =18;i<36;i++){
            pathSet2.add(listpath.get(i));
        }
        for(int i =36;i<54;i++){
            pathSet3.add(listpath.get(i));
        }
        for(int i =54;i<72;i++){
            pathSet4.add(listpath.get(i));
        }
        for(int i =72;i<90;i++){
            pathSet5.add(listpath.get(i));
        }

        int flag =0;
        Graph graph1 = new Graph(conMap, pathSet);
        Graph graph2 = new Graph(conMap2, pathSet2);
        Graph graph3 = new Graph(conMap3, pathSet3);
        Graph graph4 = new Graph(conMap4, pathSet4);
        Graph graph5 = new Graph(conMap5, pathSet5);


        ArrayList<Graph> graphs = new ArrayList<>();

        graphs.add(graph1);
        graphs.add(graph2);
        graphs.add(graph3);
        graphs.add(graph4);
        graphs.add(graph5);

        a.AstarCalculate(graphs,v2,v10,coefficientH, coefficientG);


    }
}

计算启动

package com.graph;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class MyExecutorService {

    public static void main(String[] args) {
        // public static ExecutorService newFixedThreadPool(int nThreads)
        ExecutorService pool = Executors.newFixedThreadPool(16);
       // pool.submit(new MyRunnable());
        //pool.submit(new MyRunnable());
        int flag =0;
       // while(flag<20000){
            //pool.submit(new ParallelAstarRunnable(1.0,1.0));
          //  pool.submit(new ParallelAstarRunnable(0.7,0.1));
           // pool.submit(new ParallelAstarRunnable(0.6,0.4));
           // pool.submit(new ParallelAstarRunnable(0.4,0.5));
            //pool.submit(new ParallelAstarRunnable(0.2,0.7));
           // pool.submit(new ParallelAstarRunnable(0.1,1.1));
            flag++;
       // }

       // ParallelAstarRunnable p = new ParallelAstarRunnable(1.0,1.0);
        ParallelAstarRunnable3 p3 = new ParallelAstarRunnable3(1.0,1.0);
       // p.cal();
        p3.cal();
        //结束线程池
       // pool.shutdown();
    }
}