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

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 章 最短路径算法