ダイクストラは通常、グラフ内の 2 つのノード間の最短距離を見つけるために使用されます。最小全域木を見つけるために使用できますか? もしそうなら、どのように？
編集: これは宿題ではありませんが、古い模擬試験の問題を理解しようとしています。
質問する
47702 次
5 に答える
50
答えはノーだ。その理由を確認するために、まず次のように質問を明確にしましょう。
Q: 非負の辺の重みのみを持つ接続された無向の重み付きグラフG = (V, E, w)の場合、ダイクストラのアルゴリズムによって生成された先行サブグラフは G の最小スパニング ツリーを形成しますか?
(無向グラフは有向グラフの特別なクラスであるため、無向グラフでダイクストラのアルゴリズムを使用してもまったく問題ないことに注意してください。さらに、MST は接続された無向グラフに対してのみ定義され、グラフが重み付けされていない場合は自明なので、我々の調査をこれらのグラフに限定しなければならない.)
A:ダイクストラのアルゴリズムは、すべてのステップで、いくつかのソース頂点 sに最も近い次のエッジを貪欲に選択します。これは、s がグラフ内の他のすべての頂点に接続されるまで行われます。明らかに、生成される先行サブグラフは のスパニング ツリーですがG、エッジの重みの合計は最小化されていますか?
最小スパニング ツリーを生成することが知られているプリムのアルゴリズムは、ダイクストラのアルゴリズムと非常に似ていますが、各段階で、その段階で現在動作中の MST にある頂点に最も近い次のエッジを貪欲に選択します。この観察を使用して、反例を作成しましょう。
反例: 無向グラフを考えてみましょうG = (V, E, w)。
V = { a, b, c, d }
E = { (a,b), (a,c), (a,d), (b,d), (c,d) }
w = {
( (a,b) , 5 )
( (a,c) , 5 )
( (a,d) , 5 )
( (b,d) , 1 )
( (c,d) , 1 )
}
aソース頂点として取得します。
ダイクストラのアルゴリズムはエッジを取ります{ (a,b), (a,c), (a,d) }。
したがって、このスパニング ツリーの重みの合計は5 + 5 + 5 = 15です。
プリムのアルゴリズムはエッジを取ります{ (a,d), (b,d), (c,d) }。
したがって、このスパニング ツリーの重みの合計は5 + 1 + 1 = 7です。
于 2013-12-09T22:30:39.320 に答える