データ構造とアルゴリズム総合

問題 1(100 点).
負の枝長の枝は存在するが，負の経路長のサイクルは持たない強連結な有向グラフ G = (V, E) を
考える．ここで，l(u, v) は枝 (u, v) ∈ E の長さ，d(v, w) は点 v ∈ V から点 w ∈ V への最短路長を
表すものとする．以下の問いに答えよ．
(1) グラフ G において，任意の点 v ∈ V 及び任意の枝 (u, w) ∈ E に対し，
l(u, w) + d(v, u) −　d(v, w) ≥ 0 が成り立つことを証明せよ．

(2) グラフ G において，V のすべての点 v に対して数値 s(v)が与えられているとする．さらに，
すべての枝 (u, v) ∈ E についてその長さを l(u, v) + s(u) − s(v) に変換したグラフ G を考え
る．この時，G 上において任意の 2 点 w, x 間の最短路であるパスは，G においても同じく
w, x 間の最短路であることを証明せよ．

(3) グラフ G において，v ∈ V を始点とする最短路木を求めるアルゴリズムを記述し，その計算
量を述べよ．

(4) グラフ G において，v ∈ V を始点とする最短路木が与えられている時に，別の点 w ∈ V を
始点とする最短路木を求めるアルゴリズムを記述し，その計算量を述べよ．