algorithm - 優先キューに関するダイクストラ アルゴリズムの最適化

Question

以下のコードをシミュレーションで使用します。私は何度もダイクストラ メソッドを呼び出しているため、パフォーマンスは私にとって非常に重要です。、 PriorityQueue を使用して、グラフのノードをソースまでの距離に対して昇順で維持します。PriorityQueue を使用すると、O(log n) の複雑さで最小距離のノードにアクセスできます。ただし、ノードの距離を再計算した後にノードを順番に保つには、ノードを再度追加するよりも、最初にノードを削除する必要があります。もっと良い方法があるかもしれないと思います。フィードバックをお寄せいただきありがとうございます。すべてのコミュニティに感謝します。

    public HashMap<INode, Double> getSingleSourceShortestDistance(INode sourceNode) {
    HashMap<INode, Double> distance = new HashMap<>();
    PriorityQueue<INode> pq;

   // The nodes are stored in a priority queue in which all nodes are sorted      

   according to their estimated distances.



    INode u = null;
    INode v = null;
    double alt;


    Set<INode> nodeset = nodes.keySet();
    Iterator<INode> iter = nodeset.iterator();
    //Mark all nodes with infinity
    while (iter.hasNext()) {
        INode node =  iter.next();
        distance.put(node, Double.POSITIVE_INFINITY);
        previous.put(node, null);
    }
    iter = null;

    // Mark the distance[source] as 0
    distance.put(sourceNode, 0d);


    pq = new PriorityQueue<>(this.network.getNodeCount(), new NodeComparator(distance));

    pq.addAll(nodeset);

    // Loop while q is empty
    while (!pq.isEmpty()) {
        // Fetch the node with the smallest estimated distance. 
        u = pq.peek();
        /**
         * break the loop if the distance is greater than the max net size.
         * That shows that the nodes in the queue can not be reached from
         * the source node.
         */
        if ((Double.isInfinite(distance.get(u).doubleValue()))) {

            break;
        }
        // Remove the node with the smallest estimated distance.
        pq.remove(u);

        // Iterate over all nodes (v) which are neighbors of node u
        iter = nodes.get(u).keySet().iterator();
        while (iter.hasNext()) {
            v = (INode) iter.next();
            alt = distance.get(u) + nodes.get(u).get(v).getDistance();
            if (alt < distance.get(v)) {
                distance.put(v, alt);
                //To reorder the queue node v is first removed and then inserted.
                pq.remove(v);
                pq.add(v);



            }
        }
    }



    return distance;



}

    protected static class NodeComparator<INode> implements Comparator<INode> {

    private Map<INode, Number> distances;

    protected NodeComparator(Map<INode, Number> distances) {
        this.distances = distances;
    }

    @Override
    public int compare(INode node1, INode node2) {
        return ((Double) distances.get(node1)).compareTo((Double) distances.get(node2));
    }
}