2

ここでは新しいですが、かなり長い間ゲストとして潜んでいました:)

さて、私はフィボナッチ ヒープ (Java で) を使用して、ダイクストラの最短パス アルゴリズムを実行しようとしています。いくつかの検索の後、フィボナッチ ヒープを表す 2 つの既製の実装に出くわすことができました。最初の実装は非常によくできていて、ここで見つけることができます。2 番目の実装は、あまり洗練されていないように見えますが、ここにあります。

さて、これはすべて見栄えがよく、うまく見えます。ただし、ダイクストラのアルゴリズムのバージョンにこれらの実装の1つを使用したいのですが、まだ運がありません。使用中のダイクストラの実装は次のとおりです。

public void dijkstra(Vertex source) {
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }
}

明らかなように、この実装では Java ベースの PriorityQueue クラス (バイナリ ヒープ自体に基づいていると思われます) を使用します。Java の PriorityQueue の代わりに前述のフィボナッチ ヒープ実装のいずれかを使用するように、上記のコードを変更したいと考えています。

私は多くのことを試しましたが、数行のコードを置き換えるのと同じくらい簡単だと確信していますが、それを行う方法がわかりません。

私は十分に明確であることを願っています。これは文字通り、これらのボードでの私の最初の投稿です。

どんな助けでも大歓迎です。

編集:コメントに応えて、私は自分の試みのシナリオの 1 つを使用して投稿を拡張すると考えました。

以下は、前にリンクされた 2 番目のフィボナッチ ヒープ実装を使用した、上記のダイクストラ法の修​​正版です。

public static void computePathsFibonacciHeap(Node source) {
    {
        source.minDistance = 0.;
        FibonacciHeap myHeap = new FibonacciHeap();
        myHeap.insert(source, source.minDistance);

        while (!myHeap.isEmpty()) {
            Node u = myHeap.min();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Node v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    v.minDistance = distanceThroughU;
                    myHeap.decreaseKey(v, v.minDistance);
                    v.previous = u;
                }
            }
        }
    }
}

これはほとんど疑似コードから直接変換されたものです (したがって、正しく変換しなかった可能性は十分にあります)。「decreaseKey() の値が大きくなりました」というエラーが表示されます。最小値を削除しようとすると、NullPointerException が発生します。

私は何か間違ったことをしていると確信しています。それが何であるかを知りたいです。繰り返しますが、これは 2 番目の FHeap 実装を使用しています。私は最初の実装を使用してそれを行うことを好みましたが (それはより徹底的でプロフェッショナルに見えます)、残念ながらその方法を理解できませんでした。

4

3 に答える 3

1

Double.POSITIVE_INFINITY を使用してすべてのノードをヒープに追加していないようです (距離が 0.0 のソース ノードを除く)。それが NullPointerExceptions を持っている理由です。それらは単にヒープにありません。

いくつかのオープンソースのフィボナッチ ヒープ実装でいくつかのテストを行いました。テスト自体は、Experimenting-with-dijkstras-algorithm にあります。また、これはダイスクトラのアルゴリズムの優先キュー バージョンです: PriorityQueueDijkstra.java

于 2015-02-15T18:25:16.387 に答える
0

JDK は、フィボナッチ ヒープの実装を提供しません。独自の実装を作成する必要があります。または、この投稿で見つけることができます:フィボナッチ ヒープ

あとは交換するだけ

PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();

に

 FibonacciHeap<Vertex> vertexQueue = new FibonacciHeap<>();

次にpoll、addおよびremoveメソッドの呼び出しを、提供された実装で同等のものに変更するだけです。

于 2013-03-13T17:35:28.487 に答える