0

フィボナッチ ヒープを使用したダイクストラの実装を考案しようとしています。私が理解しようとしているのは、O(logn) (削除あり) の最小距離以外に、特定のノードの隣接ノードを表すことができるかどうかです。それとも、これはフィボナッチ ヒープ構造に違反していますか? そうしないと、隣人リストとフィボナッチ ヒープを作成する必要があります。

4

1 に答える 1

0

フィボナッチ ヒープとは何かを理解していないようです。

この構造は、ダイクストラやその他の最短経路アルゴリズムとは無関係であり、最短距離で頂点を取得する時間を短縮することによって、ダイクストラのアルゴリズムを高速化するためにのみ使用されます。

フィボナッチ ヒープ構造の一部として隣人の隣接リストを維持することについて話すことはナンセンスです。

もちろん、その頂点に対応するヒープ ノード (技術的には、ヒープ構造の一部ではない) 内の各頂点に対応する隣接ノードのリストを常に維持できます。

于 2010-11-11T22:24:41.670 に答える