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

Author

Isidore, 祭音Myyura

Description

Kai

(1)

• The shortest path is \((v_4, v_2, v_1, v_3)\)
• The distance is \(5\)

(2)

Assume that there is a cycle start and end at \(v_i\) in a shortest path \(p=(v_1, ..., v_i, ..., v_i, ...v_m)\) from \(v_1\) to \(v_m\). Then,

\[ l(p) = l(v_1, \ldots, v_i) + l(v_i, \ldots, v_i) + l(v_i, \ldots, v_m) \]

Since \(l(u,v) > 0\) for any edge \((u,v) \in E\), we have \(l(v_i, \ldots, v_i) > 0\). Thus, the path \(p' = (v_1...v_i...v_m)\) of weight

\[ l(p') = l(v_1, \ldots, v_i) + l(v_i, \ldots, v_m) \]

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

(3)

Let \(p_{ijk}\) be a shortest path from vertex \(i\) to vertex \(j\) such that all intermediate are contained in \(\{1, \ldots, k\}\). By (2) we know that a shortest path does not contain the same vertex twice, hence there are two possibilities to construct \(p_{ijk}\).

1. vertex \(k\) is not a vertex on the path, then we have \(l(p_{ijk}) = \delta (i, j, k-1)\).
2. vertex \(k\) is a vertex on the path, then the path consists of a subpath from \(i\) to \(k\) and a subpath from \(k\) to \(j\). Each subpath can only contain intermediate vertices in \(\{1, \ldots , k-1\}\), and also shortest paths from \(i\) to \(k\) and \(k\) to \(j\) respectively (otherwise a shorter path from \(i\) to \(j\) can be constructed), namely they have lengths \(\delta(i, k, k-1)\) and \(\delta(k, j, k-1)\), respectively. Hence \(l(p_{ijk}) = \delta(i, k, k-1) + \delta(k, j, k-1)\).

Combining the two cases we have

\[ \delta(i,j,k) = \min (\delta(i,j,k-1), \delta(i, k, k-1) + \delta(k, j, k-1)) \]

(4)

\[ d^{(0)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & \infty & \infty \\ \infty & \infty & 0 & 2 \\ 4 & 1 & \infty & 0 \\ \end{bmatrix} \]

\[ d^{(1)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & 4 & \infty \\ \infty & \infty & 0 & 2 \\ 4 & 1 & 6 & 0 \\ \end{bmatrix} \]

\[ d^{(2)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & 4 & \infty \\ \infty & \infty & 0 & 2 \\ 4 & 1 & 6 & 0 \\ \end{bmatrix} \]

\[ d^{(3)}= \begin{bmatrix} 0 & 1 & 2 & 4 \\ 2 & 0 & 4 & 6 \\ \infty & \infty & 0 & 2 \\ 3 & 1 & 5 & 0 \\ \end{bmatrix} \]

\[ d^{(4)}= \begin{bmatrix} 0 & 1 & 2 & 4 \\ 2 & 0 & 4 & 6 \\ 5 & 3 & 0 & 2 \\ 3 & 1 & 5 & 0 \\ \end{bmatrix} \]

(5)

By the formula proposed in (3), we have

\[ \begin{align} \delta(i, k, k) &= \min (\delta(i,k,k-1), \delta(i, k, k-1)+\delta(k, k, k-1))\\ &=\delta(i, k , k-1) \end{align} \]

which means the elements in the \(k\)-th row or the \(k\)-th column stays the same when deriving \(d^{(k)}\) from \(d^{(k-1)}\).

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

(6)

(a)

\[ d[i][j] > d[i][k] + d[k][j] \]

(b)

\[ d[i][j] \leftarrow d[i][k] + d[k][j] \]