広島大学 先進理工系科学研究科 情報科学プログラム 2020年8月実施 専門科目II 問題2

Author

祭音Myyura

Description

有向グラフ を考える。 は頂点集合、 は辺集合、 は辺 の長さとする。 また、 を頂点 の隣接頂点集合とする。 この時、以下の は、 上のある頂点 を始点とし、頂点 から他の各頂点までの最短距離を求めるアルゴリズムである。

(1) Table 1 は、グラフ を入力とし、頂点 を始点とした場合の の実行の過程における、各頂点 の の値を示したものである。Table 1 を完成させよ。

(2) のすべての辺の長さが非負である場合に、 で得られる が、すべての頂点 について頂点 からの最短距離となることを証明せよ。

(3) に負の長さの辺が存在する場合には、 は からの最短距離を求められない場合があることを証明せよ。

(4) の最悪計算時間とその理由を述べよ。

---

Let be a directed graph, where is a set of nodes, is a set of edges, and is the non-negative length of edge . Let be a set of adjacent nodes of node . The following algorithm computes the shortest distance from a node to each of the other nodes.

(1) Table 1 shows the value of for each in the process of execution of , where the input graph is and the starting node is . Complete Table 1.

(2) Prove that for each stores the shortest distance from to when terminates.

(3) Prove that may not find the shortest distance if some of the edges take negative length.

(4) Derive the time complexity of .

Kai

(1)

round
1	0
2	0	4	5
3	0	4	5	7	14
4	0	4	5	7	14	14
5	0	4	5	7	13	10
6	0	4	5	7	12	10	12

(2)

Proof by contradiction:

Let denote the length of a shortest path from to . Suppose that is the first vertex extracted from for which .

Let be a shortest path from to , where satifies but does not. When is extracted from , since is adjacent to , will be updated

Now both and are in when is chosen. Note that by assumption is the first vertex extracted from for which , hence either or is chosen after , which means that . But by assumption we have , hence we have

Thus the two inequalities must be equalities,

a contradiction.

(3)

from will first develop , and will later fail to find .

(4)

If we stores the vertex set as a heap, and edges as an adjacent list, then finding of minimum takes .

Note that we need update of every , which can be done by inserting a "new vertex" of updated into heap , hence the size of is at most .

Therefore, the time complexity of is .