1

Javaプログラミング言語を使用して、正のエッジコストを持つグラフに最も効率的な最短経路アルゴリズムを実装しようとしています. 私の知る限りでは、これは優先キューとしてフィボナッチ ヒープを使用したダイクストラのアルゴリズムです。リンクに記載されているように、Keith Schwarz による次の Fibonacci Heap 実装を借りました。http://keithschwarz.com/interesting/code/?dir=fibonacci-heap

私のコードでは、この質問で提示されたダイクストラ アルゴリズムの実装も変更しました。

Java: ダイクストラのアルゴリズムを実装するためのフィボナッチ ヒープの使用

これが私の実装に基づく更新されたダイクストラです。

public static void SPFibonacciHeap() {
    {

        FibonacciHeap<Node> myHeap = new FibonacciHeap<Node>();

        //adding all nodes to the PQ (heap)
        for(int i=0; i<nodeList.size(); i++)
                    myHeap.enqueue(nodeList.get(i), nodeList.get(i).d);

        while (!myHeap.isEmpty()) {

            //deque the minimum (first iteration will be the source)
            Entry<Node> u = myHeap.dequeueMin();


            // Visit each edge connected from u
            for (AdjacentNode a : u.getValue().adjacents) {

                //getting the adjacent node
                Node v = a.node;
                Entry<Node> vEntry = new Entry<Node>(v,v.d);//WRONG

                //getting the edge weight
                double weight = a.cost;

                double distanceThroughU = u.getValue().d + weight;
                if (distanceThroughU < v.d) {
                    v.d = distanceThroughU;
                    myHeap.decreaseKey(vEntry, v.d); //SHOWS ERROR
                    v.parent = u.getValue();
                }
            }
        }
    }
}

これが私の Node と AdjacentNode クラスです。

class Node{

    Double [] label;
    double d; //node cost
    ArrayList<AdjacentNode> adjacents;
    Node parent;

    public Node(Double[] label, double d,ArrayList<AdjacentNode> adjacents)
    {
        this.label= label;
        this.d=d;
        this.adjacents=adjacents;
        parent=null;

    }




}


class AdjacentNode
{
    Node node;
    double cost;

    public AdjacentNode(Node node, double cost)
    {
        this.node= node;
        this.cost=cost;
    }
}

次の行でキーを減らしたいと思うまで、すべてうまくいきました。

myHeap.decreaseKey(vEntry, v.d);

私が直面している問題はvEntry、ヒープ内に既に存在するノードでなければならないということです。ただし、このノードをヒープから取得することはできません。これは、隣接するノードを取得するために考えられる唯一の方法はv、 node の隣接リストを使用することであるためuです。しかし、次の行では、それを新しい Entry Node として誤って表現しています。

Entry<Node> vEntry = new Entry<Node>(v,v.d);

ただし、これにより、探しているノードを持つヒープに存在するエントリではなく、探しているノードを保持する新しいエントリが作成されます。これにより、予想どおり Null ポインター例外が発生します。

この問題の解決策がわかりません。このヒープ実装では、特定のノード エントリに隣接するノード エントリを取得することはできないようですか? 誰か助けてくれませんか？ありがとうございました。

4

1 に答える 1

1

だから...それは私のコードです。:-) 私はおそらくここで助けることができると思います.

お気付きかもしれませんが、このメソッドは、エンキューしたオブジェクトに対応するフィボナッチ ヒープ内の内部エントリを表す をenqueue返します。Entry<T>その意図は、フィボナッチ ヒープに何かをエンキューするときに、保存しEntry<T>てどこかに戻して、後で使用できるようにすることです。実際、私のサイトには Dijkstra のアルゴリズムの実装もあります。私がこの作業を行った方法はMap、ノードからEntryオブジェクトに 1 秒を格納することでした。これにより、 を呼び出す必要があるときに、指定されたノードに対応する をdecreaseKey検索して、Entryそれを に渡すことができますdecreaseKey。

注意点として、フィボナッチ ヒープを使用したダイクストラのアルゴリズムは、理論上は単純なバイナリ ヒープなどを使用するよりも高速ですが、実際には、フィボナッチ ヒープの定数係数が非常に高いため、はるかに遅くなる傾向があります。これは多くの要因 (大量のポインターのジャグリング、ローカリティの低い多数のリンク構造など) によるものです。バイナリヒープ。フィボナッチ ヒープを使用したい場合でも、私が投稿した実装を最適化してみてください。生の効率ではなく、正確さと明快さを目標に書いています。

于 2016-02-29T20:25:34.057 に答える