C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト


(過去ログ 98 を表示中)
■58179 / )  n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (2回)-(2011/03/28(Mon) 15:46:15)

分類:[C/C++] 

グラフに関する質問です。

重み付きグラフ内の2点間の最短距離を求めるなら、ダイクストラ法。
全部の点を辺で結ぶ時、辺の長さの計の最短を求めるなら、最小全域木。

では辺で結ばれたn点のグラフがある時、その中から指定されたm点を選び、このm点を結ぶ最小全域木の作り方はどうなるのでしょうか?


3点を結ぶ場合はワーシャルフロイド法で最小コストを求め、3点を結ぶ最小全域木の分岐点を探せばいいだけでした。

この方法では4,5、、n-1点と一般になると手に負えません。
どなたか良い方法のご紹介をお願いします。
返信 編集キー/


管理者用

- Child Tree -