グラフの2つの互いに素なサブセットに属する任意の2つのノード間の最短経路を見つける

すべてのノードに何らかの色が割り当てられた無向グラフがあります。青い色のノードから赤い色のノードまでの最短経路を見つけなければなりません。（他の色もグラフに存在するかもしれませんが、重要ではありませんが、色の数はわかりません）どうすれば多項式時間で行うことができますか？グラフの2つの互いに素なサブセットに属する任意の2つのノード間の最短経路を見つける

出典

2012-03-14 anirudh

私はDijkstraアルゴリズムが何らかの方法でこれを解決することができると確信していますが、私はどのように考え出すことができませんでした。 – anirudh

ヒントとして、2つの新しいノードをグラフに追加します。これをsとtと呼びます。コスト0のエッジを有する各青色ノードにsを接続し、コスト0のエッジを有する各赤色ノードをtに接続する。次に、sからtへの最短経路を見つける。

希望すると便利です。

出典

2012-03-14 19:26:27 templatetypedef

ありがとう、これは確かに解決策です。 – anirudh

sノードとtノードを追加し、それらの間の最短経路（例えば、ダイクストラ）を見つけるための多項式なので、多項式となります。 – pvoosten

@lbp多項式時間で簡単に解く方法はたくさんありますが、Floyd-Warshallを使って最小距離のペア（青、赤）を見つけることができます。あなたはダイクストラをすることができます|赤| * |青|非常に非効率的であり、依然として多項式である。しかし、この答えは、多項式だけでなく、効率的な方法を提供します。 – sdcvvc

グラフの2つの互いに素なサブセットに属する任意の2つのノード間の最短経路を見つける

答えて

関連する問題