正しさの証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:11 UTC 版)
「ベルマン–フォード法」の記事における「正しさの証明」の解説
このアルゴリズムの正しさは数学的帰納法で示すことができる。以下にそれを示す。 補題: for サイクルを i 回繰り返したとき: Distance(u) が無限大でないとき、その値は s から u の何らかの経路の距離と等しい。 高々 i 個の辺からなる s から u への経路があるとき、Distance(u) は高々 i 個の辺から成る s から u への高々最短経路の距離である。 証明: 帰納法の基本ケースとして、i=0 で for サイクルを実行する前の時点を考える。すると、始点については source.distance = 0 であるから正しい。他の頂点 u については u.distance = infinity なので、これも正しい（0個の辺からなる始点から u への経路は存在しない）。 帰納ケースについては、まず第1の部分を証明する。ある頂点の距離が v.distance := u.distance + uv.weight で更新された時点を考える。帰納法上の前提により、u.distance は始点から u へのなんらかの経路の距離である。したがって u.distance + uv.weight は始点から u までの経路の長さと、そこから v までの距離を加えたもので、始点から v までの経路の距離である。 第2の部分については、高々 i 個の辺からなる始点から u への最短経路を考える。v が その経路上 u の直前の頂点だとする。すると、始点から v までの経路は高々 i-1 個の辺からなる始点から v までの最短経路となる。帰納法上の前提により、i-1 回の反復後の v.distance は高々この経路の距離である。したがって、uv.weight + v.distance は高々 s から u への経路の距離である。i-番目の反復で、u.distance は uv.weight + v.distance と比較され、uv.weight + v.distance の方が小さければその値が設定される。したがって、i 回の反復後、u.distance は高々始点から uへの最短経路の距離であり、その経路には高々 i 個の辺がある。 負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。したがって step 3 に至ったとき、それ以上の経路や距離の短縮は不可能である。逆に短縮できないとすると、頂点 v[0],..,v[k-1] の任意の閉路について、次が成り立つ。 v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight 閉路上で総和を求めると、v[i].distance の項と v[i-1 (mod k)].distance の項は相殺され、次の式が残る。 0 <= v[i-1 (mod k)]v[i].weight の 1 から k までの総和 すなわち、全ての閉路は負でない重みを持つ。
※この「正しさの証明」の解説は、「ベルマン–フォード法」の解説の一部です。
「正しさの証明」を含む「ベルマン–フォード法」の記事については、「ベルマン–フォード法」の概要を参照ください。
正しさの証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/05 08:32 UTC 版)
P を重み付き連結グラフとする。プリム法の繰り返しでは、毎回ある部分グラフからその外部へと接続している辺を探し出す。P は連結グラフなので、全ての頂点に常に道が存在する。プリム法の出力 Y に追加される辺と頂点はつねに接合しているため、Y は木である。Y1 が P の最小全域木であるとする。Y1=Y なら、Y は最小全域木である。そうでない場合、Y にあって Y1 にない辺のうち、Y の構築時に最初に追加された辺を e とし、e が追加される以前に追加された辺に接合している頂点の集合を V とする。e の端点の一方は V にあり、もう一方はそうではない。Y1 は P の全域木なので、Y1 にはその2つの端点をつなぐ道がある。その道をたどると、V 内の頂点から V 外の頂点への辺 f に必ず遭遇する。さて、Y に e を追加した時の繰り返しにおいて、e よりも f の方が重みが小さければ f が追加されていただろう。しかし f は追加されなかったので、次の結論が得られる。 w(f) ≥ w(e) Y1 から f を除いて e を追加したグラフを Y2 とする。Y2 が連結グラフであり、Y1 と同数の辺を持ち、辺の重みの総和が Y1 より小さいことは容易に示すことができる。従って、これも P の最小全域木であり、e を含み、それ以前に V の構築の際に追加された全ての辺を含んでいる。以上を繰り返し適用していくと、Y と全く同じ P の最小全域木を得られる。以上から、Y は最小全域木であることがわかる。 最小全域木問題の他のアルゴリズムとしてクラスカル法やブルーフカ法がある。
※この「正しさの証明」の解説は、「プリム法」の解説の一部です。
「正しさの証明」を含む「プリム法」の記事については、「プリム法」の概要を参照ください。
正しさの証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)
このアルゴリズムの正しさの証明は2つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。
※この「正しさの証明」の解説は、「クラスカル法」の解説の一部です。
「正しさの証明」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。
- 正しさの証明のページへのリンク
