接続されていない無向グラフを接続し、各可能性についてsrcから目的地までの最短経路を計算するための可能なすべての方法を見つけます。

Question

この問題では、切断された無向グラフと各頂点間の距離のある2D行列が与えられます。私はこの状態から接続されたグラフを作成し、可能な組み合わせごとに頂点0から頂点1までの最短経路の距離を計算するすべての可能な方法を見つけることを試みています。頂点0はソース頂点として選択され、頂点0へのパスを持つすべての頂点は接続されているとみなされ、頂点0へのパスのないすべての頂点は接続されません。すべての可能なパスを見つけるのにBFSを使用しようとしていますが、動的プログラミングを使用して最適化しますが、サブ問題とデータ構造が何であるべきかを理解できません。例えば

は、V = {0,1,2}とADJマトリックス（最初のもの）と各行列との間の距離（2 1）と、このグラフを与え：

0 1 2   0 1 2 
0 0 0 0  0 0 3 4 
1 0 0 1  1 3 0 1 
2 0 1 0  2 4 1 0 

を頂点1と2がないので私が0から1を接続する場合、最短パスの長さは3になります.0から2を接続すると、0から1までの最短パスは4 + 1になります。どちらの場合も同様です。

サブ問題は何ですか、この問題をどのように解決する必要がありますか？

Answer 1

接続されたコンポーネントをマルチグラフの1つの頂点（複数の辺が2つの頂点を結ぶことができるグラフ）に折り畳まれます。バックトラック検索を使用して、マルチグラフのすべてのスパニングツリーを列挙します。

このタスクの既成の複雑さはK！です。ここで、Kは接続されたコンポーネントの数です。

推移的閉包アルゴリズムで接続コンポーネントを計算します。