0

ShaneSaunders Dijkstra アルゴリズムにおける HeapDescの重要性と、ここでの使用方法を誰かが説明できますか? 一般的に、ダイクストラアルゴリズムがどのように機能するかを知っています。しかし、私は実装でヒープ部分を取得しません。

その大きなコード。したがって、見たい場合はリンクを投稿しています。

ここに行くhttp://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.cpp

4

3 に答える 3

1

ダイクストラでは、別の頂点に到達できる最小コストのエッジを提供する効率的なデータ構造が必要です。

ヒープはまさに、一連のエッジを格納し、最小限のコストで効率的にエッジを取得できるデータ構造です。

于 2013-01-05T11:10:31.067 に答える
1

HeapDesc はおそらくファクトリ デザイン パターンを実装して、さまざまな種類のヒープを作成します。ファイルhttp://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.hを確認すると、コンストラクターのヒープ変数がヒープ型のオブジェクトであることがわかります。

工場の設計パターンについては、この記事をご覧ください。 http://en.wikipedia.org/wiki/Factory_method_pattern

于 2013-01-05T11:18:13.477 に答える
0

ダイクストラのアルゴリズムには、多くの「コストが最も低いパス」ルックアップが含まれます。

最小または最大ルックアップは、ヒープが最適化されているもの ( O(1) ) であり、これが使用される理由です。

それ自体は、ヒープ オブジェクトを割り当てるために使用されるファクトリ メソッドのHeapDescように見えます。

Heap *newInstance(int n) const { return new T(n); }; // from heap.h
于 2013-01-05T11:09:43.150 に答える