無向の重み付きグラフG=（V、E）が与えられます。各頂点は都市を表し、aとbに接続されたエッジの重みは、都市aと都市bの間の高速ルートの構築を完了するのにかかる年数です。グラフ内の任意の2つの都市間を移動できるようになるまでの最短年数を見つけるアルゴリズムを説明してください。ルートは同時に構築されているため、3つの都市a、b、cがあり、aとbの間に重み1のエッジがあり、bとcの間に重み2のエッジがある場合、出力は2になります。
質問する
99 次
1 に答える
1
上記のコメントは正しい答えを示しています。私の意見では、これは古典的な Prim のアルゴリズムの問題のように思えます。http://en.wikipedia.org/wiki/Prim's_algorithm
于 2012-06-01T02:28:56.277 に答える