重み付けされていない無向グラフG = (V, E)が与えられます。ここで|V| <= 40,000および|E| <= 10 6 . また、 4 つの頂点a、b、a'、b'も与えられます。長さの合計が最小になるように、2 つのノード分離パスa -> a'およびb -> b'を見つける方法はありますか?
最初に考えたのは、最初に最短パスa -> a'を見つけ、それをグラフから削除してから、最短パスb -> b'を見つけることでした。この貪欲なアプローチはうまくいかないと思います。
注:アプリケーション全体を通して、aとbは固定されていますが、a 'とb'はクエリごとに変化するため、効率的なクエリを提供するために事前計算を使用するソリューションが望ましいでしょう。また、実際のパスではなく、長さの最小合計のみが必要であることに注意してください。
ヘルプ、アイデア、または提案をいただければ幸いです。よろしくお願いします！
これは、最短エッジ独立パスの問題に還元される場合があります。
a = bまたはa' = b' の場合、前の質問とまったく同じ問題が発生します(これは最小コスト フローの問題であり、各エッジのフロー容量を 1 に割り当て、次に a を検索することで解決できます)。フロー = 2 の場合の a と b 間の最小コスト フロー)。a != bの場合、共通のソース ノードを作成し、a と b の両方をそれに接続します。a' != b' の場合、共通の宛先ノードで同じことを行います。
ただし、a != bかつa' != b' の場合、最小コスト フロー問題は適用できません。代わりに、この問題はマルチ商品フロー問題として解決される可能性があります。
私の以前の (間違った) 解決策は、( a , b ) と ( a' , b' ) の両方のペアを共通の送信元/宛先ノードに接続してから、最小コストのフローを見つけることでした。次のグラフは、このアプローチの反例です。
これはどう？a1 -> a2 から BFS (幅優先検索) トラバーサルを実行し、パスを削除して BFS b1 -> b2 を計算します。ここでグラフをリセットし、最初に b1->b2 で同じことを行い、パスを削除してから a1->a2 を削除します。合計が最小であれば、それが答えです。