1

2 つのノード間に複数のアーチを持つことができるグラフが与えられました。

例 ：

4 ノード 1->2 2->3 3->4 3->4 1->4

ノード A からノード B までの道路の数を求める最適な方法はどれですか?

この例の答えは 3 です: 1->2->3->4 ; 1->2->3->4 および 1->4

ノードとアーチの制限は 1 000 000 です

私は総当たりアルゴリズムで考えているだけです。

他のアイデアはありますか？編集：

グラフは非循環です

4

2 に答える 2

1

グラフが循環的である場合、結果は+無限大になります。これは、サイクルで好きなだけ実行できるためです。

非巡回有向グラフで機能する可能性のある1つのアイデア：

  • 接続されている2つのノードについて、親ノードが常に子ノードの前に来るように、すべてのノードを並べ替えます。
  • すべてのノードに0を割り当てます
  • 開始ノードに1を割り当てます
  • 開始ノードから順にノードを繰り返し処理します。
    • ノードがエンドノードの場合は完了です
    • このノード（つまり、親）で開始するForeach接続を実行します
      • 現在のノードの値を子ノードに追加します
  • エンドノードに割り当てられた番号は、希望する結果です

ただし、ノードでの順序付けは簡単ではありません。ただし、DAGを使用する場合の一般的な問題であるため、そのためのアルゴリズムを見つけることができると確信しています。

于 2011-05-28T09:59:33.217 に答える
0

最適な方法はありません。この問題はNP完全問題です。http://en.wikipedia.org/wiki/Feedback_vertex_set

あなたは良い解決策を見つけることができるだけです

于 2011-05-28T10:00:54.823 に答える