慶應SFC　環境情報学部　情報入試　2017年　大問Ⅴ　過去問解説

(ア)
まずアルゴリズムの大枠を掴まないと解答できない。

アルゴリズムは
1人からなる集合Mから始め
友人関係により1つずつ距離を伸ばしていくことで集合Mを拡大していき
M=Gになるまで処理を繰り返す
ということである。
このとき、新たに増える友人の集合Nを考えることで、ステップ2のtが選べるようになるわけである。
また、ステップ3のuは実際には選ぶ必要がないから、処理Cの実行回数を出力すればよい。

解答は以下である。

Gから任意の要素sを取り出し、変数Mの値を{s}とする
M≠Gが成り立つ間、次の処理Aを繰り返す
処理Aの始め
変数Nの値をMとする
すべてのに対して、次の処理Bを繰り返す
処理Bの始め
Nの値をにする
処理Bの終わり
Mの値をにする
処理Aの終わり
Nから任意の要素tを取り出し、Mの値を{t}とする
変数iの値を0とする
M≠Gが成り立つ間、次の処理Cを繰り返す
処理Cの始め
すべてのに対して、次の処理Dを繰り返す
処理Dの始め
Mの値をにする
処理Dの終わり
iの値をi+1にする
処理Cの終わり
iの値を結果として出力する

(イ)

d(v,w)>d(t,u)
と仮定し矛盾を示している。

d(v,w)≧d(v,x)

条件αより
d(s,t)=d(s,a)+d(a,t)≧d(s,w)=d(s,a)+d(a,b)+d(b,w)
条件γより
d(v,w)=d(v,b)+d(b,w)≧d(v,t)=d(v,b)+d(b,a)+d(a,t)
である。

d(a,t)≧d(a,b)+d(b,w)
d(b,w)≧d(b,a)+a(a,t)
が成り立つので
2d(a,b)≦0
d(a,b)≦0
である。

条件αより
d(s,t)=d(s,c)+d(c,t)≧d(s,w)=d(s,c)+d(c,w)
であるから
d(s,t)≧d(s,w)
である。
条件γより
d(v,w)=d(v,c)+d(c,w)≧d(t,v)=d(v,c)+d(c,t)
であるから
d(v,w)≧d(s,t)
である。

d(s,t)≦d(v,s)
とすると
d(s,t)=d(v,w)
であるのが分かる。

このとき、特に
d(c,t)≧d(c,w)
d(c,w)≧d(c,t)
が成り立っているから
d(c,t)=d(c,w)
も成り立つ。

すると、条件βより
d(t,u)≧d(v,t)=d(v,c)+d(c,t)=d(v,c)+d(c,w)=d(v,w)
が成り立つので、最初の仮定に反する。