1

割り当てのために、最小ヒープとして実装された優先キューを使用してダイクストラのアルゴリズムを実装する必要があります。距離テーブルと未処理の頂点の順序付けられていない配列を使用する実装が既にあります。（ここのページの下部に向かって説明されているように）。

入力ファイルの例を以下に示します。最初の行は頂点の数で、その後の各行はソース、宛先、重みです。

3
1 2 3
3 2 1
1 3 1

私の最初の考えは、グラフの各エッジをヒープのノードとして扱うことでしたが、テスト ファイルの 1 つに 15677372 個のエッジがあり、すぐに segfault がなければ配列を大きくすることさえできないため、それは正しくありません。未処理の頂点の配列を使用してメソッドを実装した後、どうにかしてその配列をヒープに置き換える必要があるようですが、その方法がわかりません。

誰かが私を正しい方向に向けることができますか?

4

1 に答える 1

0

通常、ダイクストラのアルゴリズムでは、プライオリティ キューはグラフ内のノードと、そのノードまでのこれまでの最適な推定距離を保持します。標準的な手法は、グラフ内のすべてのノードを優先キューに最初に距離 ∞ でエンキューし、次にキューのキーの減少操作を使用して必要に応じてノードを下げることです。

これは多くの場合、メモリの観点からは完全に実行不可能であるため、別の解釈として、最初はキューを空のままにしてから、距離 0 の開始ノードでシードします。ノードを処理するたびに、その各ノードの距離推定を更新します。隣接するノード。これは次のように行います。

  • ノードがすでに優先キューにある場合は、reduce-key を使用してノードの距離を下げることができます。
  • ノードがまだ優先度キューにない場合は、必要な優先度で挿入します。

これにより、極端に密集していないグラフの優先キューが小さく保たれます。

お役に立てれば！

于 2013-05-08T02:53:53.387 に答える