Spaghetti Source - 木の直径

説明 非負の重みを持つ無向の木が与えられたとき，木の直径，すなわち最遠頂点間距離を求める． アルゴリズム自体はシンプルである．まず適当な頂点 s から探索を行い，最も遠い頂点 u を求める．次に u から探索を行い，最も遠い頂点 v を求める．このとき (u, v) は最遠頂点対である． 実行時間が O( E ) となることは明らかである．探索に深さ優先探索を用いれば，定数も（行数も）小さくすむ．そこで以下アルゴリズムの正当性を証明する． アルゴリズムの正当性のためには，木の最遠頂点対を x, y としたとき，x または y として s からの最遠頂点 u を選んでもかまわないことを証明すれば十分である．s からの最遠頂点を u とし，s からの経路で，u と x が分かれる点を t と置く．y の位置について，次のように場合わけを行う． y が s-t 間にある場合：y を s に取り直

[cocodrips]

へえ・・・