跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-2

Author​

Isidore, 祭音Myyura

Description​

を有向グラフとする。 ここで、 は の頂点集合、 は の辺集合である。 頂点 から頂点 への有向辺は順序対 で表され、距離 を持つ。 頂点は から で番号付けられており、 である。 有向グラフの例を図１に示す。 各辺に付された数値はその辺の距離を表す。

頂点 から頂点 へと有向辺を辿って到達できるとき、この経路 を で表す。 を除く の頂点を中間頂点と呼ぶ。 経路 の距離は で与えられる。 頂点 から頂点 への最短経路は、頂点 から頂点 への全ての経路のうち距離が最小のものである。

(1) 図１のグラフにおける頂点４から頂点３への最短経路とその距離を求めよ。

(2) 経路 は、 のとき、閉路を含むという。 任意の最短経路が閉路を含まないことを証明せよ。

の全ての頂点対に対して最短経路の距離を求める問題を考える。 具体的には、頂点番号を利用した動的計画法に基づくアルゴリズムを作る。 全ての中間頂点が に含まるという制約下での頂点 から頂点 への最短経路の距離を とする ()。 条件を満たす経路が存在しないとき、 とする。 また とする。 のときは、中間頂点は存在しないとする。 を使うと、元の問題は全ての について を求めることとみなせる。

(3) のとき が成り立つことを示せ。

(4) はサイズ の２次元配列であり、その要素の値は であるとする。 ただし、配列は１で始まるインデックス方式とする。 図１のグラフに対して、 をこの順番で求めることで、全ての頂点対に対して最短経路の距離を求めよ。

(5) (4) はこのアルゴリズムが 個の２次元配列を必要とすることを示唆するが、実際には１個の２次元配列を用意すれば済むことを示せ。

(6) (5) の結果を用いると次のアルゴリズムを導ける。下の空欄 (a) および (b) を埋めよ。

Kai​

(1)​

  • The shortest path is .
  • The distance is .

(2)​

Assume that there is a cycle start and end at in a shortest path from to . Then,

Since for any edge , we have . Thus, the path of weight

is shorter than , which leads to a contradiction with the assumption that is a shortest path. Therefore, no shortest path contains a cycle.

(3)​

Let be a shortest path from vertex to vertex such that all intermediate are contained in . By (2) we know that a shortest path does not contain the same vertex twice, hence there are two possibilities to construct .

  1. vertex is not a vertex on the path, then we have .
  2. vertex is a vertex on the path, then the path consists of a subpath from to and a subpath from to . Each subpath can only contain intermediate vertices in , and also shortest paths from to and to respectively (otherwise a shorter path from to can be constructed), namely they have lengths and , respectively. Hence .

Combining the two cases we have

(4)​

(5)​

By the formula proposed in (3), we have

which means the elements in the -th row or the -th column stays the same when deriving from .

Hence we can derive each new value in-place. Thus, only one array is required.

(6)​

  • (a)
  • (b)