4

DAG G では、重み付けされたエッジが負ではない場合、G の 2 つの頂点間の最大重み付けパスをどのように見つけますか?

君たちありがとう！

4

2 に答える 2

6

これは、トポロジカル ソートを使用して O(n + m) 時間 (n はノードの数、m はエッジの数) で解決できます。逆グラフでトポロジカル ソートを実行することから始めます。これにより、すべての子が訪問される前にどのノードも訪問されないように、すべてのノードが順序付けられます。

ここで、そのノードから始まる最大の重みのパスの重みですべてのノードにラベルを付けます。これは、次の再帰的な観察に基づいて行われます。

  • シンク ノード (出力エッジのない任意のノード) から始まる最大の重みのパスの重みはゼロです。これは、そのノードから始まる唯一のパスが、そのノードだけの長さゼロのパスであるためです。
  • 他のノードから始まる最大の重みのパスの重みは、ノードへの出力エッジをたどり、そのノードから最大の重みのパスを取ることによって形成されるパスの最大の重みによって与えられます。

ノードをリバース トポロジカルに並べ替えているため、エッジをたどってそのノードのエンドポイントで最も重いパスのコストを調べようとすると、すべてのノードを確実な順序で訪問できます。そのノードから始まる最大重みパスを計算しました。これは、逆トポロジーの並べ替え順序を取得したら、次のアルゴリズムをその順序ですべてのノードに適用できることを意味します。

  1. ノードに出力エッジがない場合は、そのノードから始まる最も重いパスの重み (d(u) で示される) をゼロとして記録します。
  2. それ以外の場合、現在のノード u を離れる各エッジ (u, v) について、l(u, v) + d(v) を計算し、d(u) をこの方法で得られた最大値に設定します。

このステップを完了すると、すべてのノードを最後に 1 回パスし、任意のノードで達成された d の最大値を返すことができます。

このアルゴリズムの実行時間は、次のように分析できます。トポロジカル ソートの計算は、さまざまな方法を使用して O(n + m) 時間で実行できます。次に、各ノードと各ノードからの各出力エッジをスキャンすると、各ノードとエッジに 1 回だけアクセスします。これは、ノードに O(n) 時間、エッジに O(m) 時間を費やすことを意味します。最後に、O(n) 時間かけて、O(n) かかる最大の重みのパスを見つけます。これにより、O(n + m) 時間の総計が得られます。これは、入力のサイズに比例します。

于 2011-03-24T20:58:35.457 に答える
1

単純なブルート フォース アルゴリズムは、再帰関数を使用して記述できます。空のベクター (C++ の場合: std::vector) から始めて、最初のノードを挿入します。次に、次のことを行う引数としてベクトルを使用して再帰関数を呼び出します。

  • すべてのネイバーをループし、ネイバーごとにループする
    • ベクトルをコピーする
    • 隣人を追加
    • 自分に電話する

また、総重みを引数として再帰関数に追加し、再帰呼び出しごとに重みを追加します。

関数は、終了ノードに到達するたびに停止する必要があります。次に、合計重量をこれまでの最大重量と比較し (グローバル変数を使用)、新しい合計重量が大きい場合は、最大重量を設定してベクトルを保存します。

後は君しだい。

于 2010-11-11T19:47:53.320 に答える