1

たくさんのノードやエッジなどを含むGraphクラスがあり、ダイクストラのアルゴリズムを実行しようとしています。まず、すべてのノードを優先キューに追加します。各ノードには、すでに「既知」であるかどうかを示すブールフラグ、その前にあるノードへの参照、およびソースノードからの長さを格納するintdistフィールドがあります。すべてのノードをPQに追加し、ソースノードに適切にフラグを付けた後、最初に間違ったノードがPQから削除されていることに気付きました。distフィールドが最小のノードが最初にオフになるはずです（ソースを除いてすべて非常に高い数に初期化されるため、PQから外れる最初のノードがソースになるはずです...一部のノードではない場合を除きます）理由）。以下は、アルゴリズムのコードと、それに続くNodeクラス内のcompareメソッドです。

    public void dijkstra() throws IOException {
    buildGraph_u();
    PriorityQueue<Node> pq = new PriorityQueue<>(200, new Node());

    for (int y = 0; y < input.size(); y++) {
        Node v = input.get(array.get(y));
        v.dist = 99999;
        v.known = false;
        v.prnode = null;
        pq.add(v);
    }

    source.dist = 0;
    source.known = true;
    source.prnode = null;
    int c=1;
    while(c != input.size()) {
        Node v = pq.remove();
        //System.out.println(v.name);
                    //^ Prints a node that isn't the source
        v.known = true;
        c++;
        List<Edge> listOfEdges = getAdjacent(v);
        for (int x = 0; x < listOfEdges.size(); x++) {
            Edge edge = listOfEdges.get(x);
            Node w = edge.to;
            if (!w.known) {
                int cvw = edge.weight;
                if (v.dist + cvw < w.dist) {
                    w.dist = v.dist + cvw;
                    w.prnode = v;
                }
            }
        }
    }
}

public int compare (Node d1, Node d2) {
       int dist1 = d1.dist;
       int dist2 = d2.dist;
       if (dist1 > dist2) 
         return 1;
       else if (dist1 < dist2) 
         return -1;
       else 
         return 0;
     }

誰かが私のPQの問題を見つけるのを手伝ってもらえますか？

4

1 に答える 1

2

優先キューは、要素を挿入した後、順序が変更されないという仮定を使用します。

したがって、すべての要素を優先キューに挿入する代わりに、次のことができます。

  1. 1つのノードから始めます。

  2. 優先キューが空でないときにループします。

  3. 要素が「既知」の場合は、何もしません。

  4. 距離が短い場合は、「適切な」重みで優先キューに追加してください。

  5. したがって、sth elseを優先キューに格納する必要があります。ペア：挿入時の距離、ノード自体。

于 2012-11-27T23:10:42.223 に答える