東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題10

标签：

• Tokyo-University
• Shortest-Path-Problem

Author

zephyr

Description

We define the shortest distance from a vertex $i$ to a vertex $j$ on a graph as the number of edges in a path from $i$ to $j$ that contains the smallest number of edges, except that the shortest distance is $+\infty$ when no such path exists and that it is $0$ when $i$ and $j$ are identical.

(1) Let us consider the directed graph shown below.

• (A) Show the adjacency matrix.
• (B) Show a matrix $\mathbf{S}$, whose element $s_{i,j}$ is the shortest distance from a vertex $i$ to a vertex $j$.

(2) Suppose we are given a simple directed graph $G = (V, E)$, where the vertex set $V = \{1, 2, \ldots, n\}$ and $E$ is the edge set. $E$ is represented by a matrix $\mathbf{D^{(0)}} = (d_{i,j}^{(0)})$, where

$$d_{i,j}^{(0)} = \begin{cases} 0 & \text{(if } i = j \text{)} \\ 1 & \text{(if an edge } i \to j \text{ exists)} \\ +\infty & \text{(otherwise)} \end{cases}$$

• (A) Let $\mathbf{V_{i,j}^{(k)}} = \{1, 2, \ldots, k\} \cup \{i, j\}$. Let $\mathbf{E_{i,j}^{(k)}}$ be the set of edges in $E$ that start from and end at a vertex in $\mathbf{V_{i,j}^{(k)}}$. Let $d_{i,j}^{(k)}$ be the shortest distance from a vertex $i$ to a vertex $j$ on a directed graph $G_{i,j}^{(k)} = (\mathbf{V_{i,j}^{(k)}}, \mathbf{E_{i,j}^{(k)}})$, and let $\mathbf{D^{(k)}} = (d_{i,j}^{(k)})$. Express $\mathbf{D^{(1)}}$ in terms of $\mathbf{D^{(0)}}$.

• (B) $\mathbf{D^{(k+1)}}$ can be computed from $\mathbf{D^{(k)}}$ as follows. Fill in the two blanks.

$$d_{i,j}^{(k+1)} = \min \left( d_{i,j}^{(k)}, \boxed{\phantom{ddd}} + \boxed{\phantom{ddd}} \right)$$

• (C) Given $G$, show an algorithm to compute the all-pair shortest distances, and find its time complexity with regard to $n$.

---

我们将从顶点 $i$ 到顶点 $j$ 的最短距离定义为图中从 $i$ 到 $j$ 的包含最少边数的路径中的边数，除了当不存在这样的路径时最短距离为 $+\infty$，以及当 $i$ 和 $j$ 相同时为 $0$。

(1) 让我们考虑下图所示的有向图。

• (A) 显示邻接矩阵。
• (B) 显示一个矩阵 $\mathbf{S}$，其元素 $s_{i,j}$ 是从顶点 $i$ 到顶点 $j$ 的最短距离。

(2) 假设我们有一个简单的有向图 $G = (V, E)$，其中顶点集 $V = \{1, 2, \ldots, n\}$ 和边集 $E$。$E$ 由矩阵 $\mathbf{D^{(0)}} = (d_{i,j}^{(0)})$ 表示，其中

$$d_{i,j}^{(0)} = \begin{cases} 0 & \text{（如果 } i = j \text{）} \\ 1 & \text{（如果存在边 } i \to j \text{）} \\ +\infty & \text{（否则）} \end{cases}$$

• (A) 设 $\mathbf{V_{i,j}^{(k)}} = \{1, 2, \ldots, k\} \cup \{i, j\}$。设 $\mathbf{E_{i,j}^{(k)}}$ 为从顶点 $\mathbf{V_{i,j}^{(k)}}$ 中的顶点出发并结束于顶点的边集。设 $d_{i,j}^{(k)}$ 为有向图 $G_{i,j}^{(k)} = (\mathbf{V_{i,j}^{(k)}}, \mathbf{E_{i,j}^{(k)}})$ 上从顶点 $i$ 到顶点 $j$ 的最短距离，并设 $\mathbf{D^{(k)}} = (d_{i,j}^{(k)})$。用 $\mathbf{D^{(0)}}$ 表示 $\mathbf{D^{(1)}}$。
• (B) $\mathbf{D^{(k+1)}}$ 可以从 $\mathbf{D^{(k)}}$ 计算如下。填写两个空格。

$$d_{i,j}^{(k+1)} = \min \left( d_{i,j}^{(k)}, \boxed{\phantom{ddd}} + \boxed{\phantom{ddd}} \right)$$

• (C) 给定 $G$，展示一个算法来计算所有对的最短距离，并找到其关于 $n$ 的时间复杂度。

Kai

(1)

(A)

The adjacency matrix $\mathbf{A}$ for the graph is a square matrix where the element $a_{i,j}$ is 1 if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise.

$$\mathbf{A} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{bmatrix}$$

(B)

The matrix $\mathbf{S}$ will be computed using the Floyd-Warshall algorithm. The element $s_{i,j}$ is the shortest distance from vertex $i$ to vertex $j$.

1. Initialize $\mathbf{S}$ with:

   • $s_{i,j} = 0$ if $i = j$
   • $s_{i,j} = 1$ if there is an edge from $i$ to $j$
   • $s_{i,j} = +\infty$ otherwise

2. Update $\mathbf{S}$ using the Floyd-Warshall algorithm:

   $$s_{i,j} = \min(s_{i,j}, s_{i,k} + s_{k,j})$$

The final $\mathbf{S}$ matrix is:

$$\mathbf{S} = \begin{bmatrix} 0 & 1 & 2 & 4 & \infty & 3 & \infty \\ 2 & 0 & 1 & 3 & \infty & 2 & \infty \\ 1 & 2 & 0 & 2 & \infty & 1 & \infty \\ 1 & 2 & 3 & 0 & \infty & 4 & \infty \\ 1 & 2 & 3 & 1 & 0 & 4 & \infty \\ 2 & 3 & 4 & 1 & \infty & 0 & \infty \\ 2 & 3 & 4 & 2 & 1 & 1 & 0 \\ \end{bmatrix}$$

(2)

(A)

The matrix $\mathbf{D^{(1)}}$ is computed by considering paths that may pass through the vertex 1.

$$d_{i,j}^{(1)} = \min(d_{i,j}^{(0)}, d_{i,1}^{(0)} + d_{1,j}^{(0)})$$

(B)

To find $\mathbf{D^{(k+1)}}$ from $\mathbf{D^{(k)}}$, use:

$$d_{i,j}^{(k+1)} = \min(d_{i,j}^{(k)}, d_{i,k+1}^{(k)} + d_{k+1,j}^{(k)})$$

(C)

The Floyd-Warshall algorithm is suitable for computing all-pair shortest distances:

1. Initialize $\mathbf{D}$ where $d_{i,j}$ is 0 if $i = j$, 1 if there is an edge $i \to j$, and $+\infty$ otherwise.
2. Update $\mathbf{D}$ using: $d_{i,j} = \min(d_{i,j}, d_{i,k} + d_{k,j})$ for all vertices $k$ from 1 to $n$.

Algorithm:

function FloydWarshall(V, E):
    let D be a |V| x |V| matrix of minimum distances
    for each vertex v in V:
        D[v][v] = 0
    for each edge (u, v) in E:
        D[u][v] = 1
    for each k from 1 to |V|:
        for each i from 1 to |V|:
            for each j from 1 to |V|:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

Time Complexity:

The time complexity of the Floyd-Warshall algorithm is $O(|V|^3)$ because it involves three nested loops, each running $n$ times.

Knowledge

最短路径 Floyd-Warshall算法 图论

重点词汇

• adjacency matrix 邻接矩阵
• shortest distance 最短距离
• edge 边
• vertex 顶点

参考资料

1. 《算法导论》 第 25 章 最短路径算法