この問題を視覚化するのに問題があります。ヒープ/優先度キューを使用して有向グラフを表示
私は有向グラフを持っています。 Dijskraのアルゴリズムを使ってこのグラフをスキャンし、最短経路を印刷する必要があります。私はヒープ/プライオリティキューを使用しなければなりません、そして、私の現在の知識から、私はこれらが同じことであることを知っています。
ただし、グラフは2つ以上の子を持つことができ、ヒープは2つの子ノードしか持つことができません。これをヒープ形式にすると、他の子（エッジ）はどうなりますか？
ヒープの表現は、とにかくグラフの構造と相関しません。
あなたはグラフで作業しています。最小距離を持つ頂点を見つけて、そこから最小距離を決定する際に使用する必要があります。ヒープは、あなたがそれを得るのを手伝っています。それ以上のことはありません。
このヒープでは、レイヤーはグラフの階層を表しておらず、ヒープのレイヤーは単にのノードの値がその子の値より小さくなるという性質を持っています。それでおしまい。グラフ内の兄弟がヒープで親子関係にある可能性があります。
ヒープワークを作成したり、Dijkstraを作成するには、ヒープでグラフ構造を模倣する必要があると考える必要はありません。それはそれを行う方法ではありません（あなたもそれを行うことはできません）。
これをヒープフォーマットにすると、他の子（エッジ）はどうなりますか？
したがって、ヒープにはルートノードがあり、ヒープの子ノードのノードの値は最小のパスに従って更新されますか？最小のパスを選択するには、ヒープルートノードの2人の子供？ minヒープを仮定します。 – hippoman
@hippoman：ヒープに挿入するとそれだけです。次に、最小距離に基づいてヒープからポップします。それはトリックをやっています。ヒープを使って作業しているときに、グラフがどのようになっているかを覚えておく必要はありません。それでおしまい。 – coderredoc
私は、グラフを表現するためにヒープを使用せず、可能な次の候補の集合を表すためにヒープを使用せず、最短距離で並べ替えるという誤解があると思います。ヒープ内のエッジは、グラフ内のエッジとは完全に無関係です。 – happydave